A heuristic for parallel machine scheduling with agreeable due dates to minimize the number of late jobs. (English) Zbl 0827.90075
Summary: Given a set of identical parallel machines and a set of jobs with different due dates and release times, we consider the problem of finding a schedule such that the number of late jobs is minimized, where the given due dates and release times are assumed to be agreeable. A heuristic algorithm is presented and a dynamic programming lower bounding procedure is developed. Computational experiments are performed to show the effectiveness of the heuristic.
References:
| [1] | Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Graves, S. G.; Kan, A. H.G. Rinnooy; Zipkin, P. H., Handbooks in Operations Research and Management Science, Vol. 4 (1993), North Holland: North Holland Amsterdam), 445-570 · Zbl 0798.90028 |
| [2] | Moore, J. M., An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs, Mgmt Sci., 15, 102-109 (1968) · Zbl 0164.20002 |
| [3] | Maxwell, W. L., On sequencing \(n\) jobs on one machine to minimize the number of late jobs, Mgmt Sci., 16, 295-297 (1970) · Zbl 0191.48402 |
| [4] | Sturm, L. B.J. M., A simple optimality proof of Moore’s sequencing algorithm, Mgmt Sci., 17, 116-118 (1970) · Zbl 0211.52001 |
| [5] | Sidney, J. B., An extension of Moore’s due date algorithm, (Elmaghraby, S. E., Symp. Theory of Scheduling and Its Applications. Symp. Theory of Scheduling and Its Applications, Lecture Notes in Economics and Mathematical Systems, 86 (1973), Springer: Springer Berlin), 393-398 · Zbl 0273.90032 |
| [6] | Monma, C. L., Linear-time algorithms for scheduling on parallel processors, Ops Res., 30, 116-124 (1982) · Zbl 0481.90048 |
| [7] | Lawler, E. L.; Martel, C. U., Preemptive scheduling of two uniform machines to minimize the number of late jobs, Ops Res., 37, 314-317 (1989) · Zbl 0672.90071 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [9] | Kise, H.; Ibaraki, T.; Mine, H., A solvable case of the one-machine scheduling problem with ready and due times, Ops Res., 26, 121-126 (1978) · Zbl 0377.90054 |
| [10] | Lawler, E. L., Scheduling a single machine to minimize the number of late jobs (1982), Computer Science Division, University of California: Computer Science Division, University of California Berkeley, Preprint · Zbl 0709.90064 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
