计算机科学
单机调度
调度(生产过程)
作业车间调度
拖延
到期日
地铁列车时刻表
作者
Chris N. Potts,L Van Wassenhove
出处
期刊:Management Science
[Institute for Operations Research and the Management Sciences]
日期:1988-07-01
卷期号:34 (7): 843-858
被引量:74
标识
DOI:10.1287/mnsc.34.7.843
摘要
This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given.
科研通智能强力驱动
Strongly Powered by AbleSci AI