×

Performance analysis of active schedules in identical parallel machine. (English) Zbl 1150.90378

Summary: Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs’ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Bellman, A. O. Esogbue, I. Nabeshima. Mathematical Aspects of Scheduling and Applications[M]. Oxford: Pergamon Press, 1982.
[2] A. H. G. Kan Rinnooy. Machine Scheduling Problems: Classification, Complexity and Computations[M]. Hague: Martinus Nijhoff, 1976.
[3] J. Riezebos, G. J. C. Gaalman. Time lag size in multiple operations flow shop scheduling heuristics[J]. European Journal of Operational Research, 1998, 105(1): 72–90. · Zbl 0957.90055 · doi:10.1016/S0377-2217(97)00025-8
[4] K. Fleszar, K. S. Hindi. Solving the resource-constrained project scheduling problem by a variable neighbourhood search[J]. European Journal of Operational Research, 2004, 115(2): 402–413. · Zbl 1045.90028 · doi:10.1016/S0377-2217(02)00884-6
[5] C. Chekuri, S. Khanna. Approximation algorithms for minimizing average weighted completion time[M]//Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Florida: CRC Press, 2004.
[6] L. A. Hall, A. S. Schulz, D. B. Shmoys, et al. Scheduling to minimize average completion time: off-line and online approximation algorithms[J]. Mathematics of Operations Research, 1997, 22(3): 513–544. · Zbl 0883.90064 · doi:10.1287/moor.22.3.513
[7] C. Wang, Y. Xi. A Rolling Optimization algorithm based on collision window for single machine scheduling problem[J]. Journal of Systems Engineering and Electronics, 2005, 16(4): 816–822.
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.