×

Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags. (English) Zbl 0866.90072

Summary: This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs.

MSC:

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

References:

[1] Aanen, E., Planning and scheduling in a flexible manufacturing system, PhD thesis, Faculty of Mechanical Engineering, University of Twente, Enschede, the Netherlands, 1988.
[2] Balas, E., Lenstra, J. K., and Vazacopoulos, A., ?The One Machine Problem with Delayed Precedence Constraints and its use in Job Shop Scheduling?, Management Science, Vol. 41, No. 1, 1995, pp. 94-109. · Zbl 0824.90076 · doi:10.1287/mnsc.41.1.94
[3] Dell’Amico, M., ?Shop Problems with Two Machines and Time Lags?, Internal Report No.93/20, Department of Electronics and Information, Milan Polytechnic, Milan, Italy, 1993.
[4] Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G., ?Optimization and approximation in deterministic sequencing and scheduling: A survey,? Annals of Discrete Mathematics, Vol. 5, 1979, pp. 287-326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[5] Johnson, S. M., ?Optimal two and three stage production schedules with setup times included,? Naval Research Logistics Quarterly, Vol. 1, No. 1, 1954, pp. 61-68. · Zbl 1349.90359 · doi:10.1002/nav.3800010110
[6] Kern, W., and Nawijn, W.M., ?Scheduling Multi-operation Jobs with Time-lags on a Single Machine?, Working paper University of Twente, Enschede, the Netherlands, 1991.
[7] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B., ?Sequencing and scheduling: algorithms and complexity,? in Graves S. C., et al., Handbook of Operations Research, Vol. 4, Elsevier, Amsterdam, 1993, pp. 445-552.
[8] Riezebos, J., Gaalman, G., and Gupta, J. N. D., ?Flowshop scheduling with multiple operations and time-lags,? Journal of Intelligent Manufacturing, Vol. 6, 1995, pp. 105-115. · doi:10.1007/BF00123682
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.