×

Two-machine flowshop scheduling with availability constraints. (English) Zbl 0971.90031

Summary: The majority of the scheduling literature carries a common assumption that machines are available all the time. However, this availability assumption may not be true in real industry settings, since a machine may become unavailable during certain periods of time when, for instance, a machine breakdown or a preventive maintenance activity is scheduled. Although the problem is realistic and important, it is relatively new and unstudied. In this paper, we study the two-machine flowshop problem under the assumption that the unavailable time is known in advance. We assume that if a job cannot be finished before the next down period of a machine then the job will have to partially restart when the machine has become available again. We call our model semiresumable. Our model contains two important special cases: resumable where the job can be continued without any penalty and nonresumable where the job needs to totally restart. We study the problem where an availability constraint is imposed only on one machine as well as on both machines. We provide complexity analysis, develop a pseudo-polynomial dynamic programming algorithm to solve the problem optimally and also propose heuristic algorithms with an error bound analysis.

MSC:

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

References:

[1] Adiri, I.; Bruno, J.; Frostig, E.; Rinnooy Kan, A. H.G, Single machine flow-time scheduling with a single breakdown, Acta Informatica, 26, 679-696 (1989) · Zbl 0657.68033
[2] Baker, K., 1995. Elements of Sequencing and Scheduling. Amons Tuck School, Hanover, NH; Baker, K., 1995. Elements of Sequencing and Scheduling. Amons Tuck School, Hanover, NH
[3] Dudek, R. A.; Pankwalkar, S. S.; Smith, M. L., The lessons of flowshop scheduling research, Operations Research, 40, 7-13 (1992) · Zbl 0825.90554
[4] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041
[5] Hall, L. A., A polynomial approximation scheme for a constrained flowshop scheduling problem, Mathematics of Operations Research, 19, 68-85 (1994) · Zbl 0821.90066
[6] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[7] Lee, C.-Y, Parallel machines scheduling with non-simultaneous machine available time, Discrete Applied Mathematics, 30, 53-61 (1991) · Zbl 0722.90032
[8] Lee, C.-Y., 1996. Machine scheduling with an availability constraint (special issue on Optimization on Scheduling Applications). Journal of Global Optimization 9, 395-416; Lee, C.-Y., 1996. Machine scheduling with an availability constraint (special issue on Optimization on Scheduling Applications). Journal of Global Optimization 9, 395-416 · Zbl 0870.90071
[9] Lee, C.-Y, Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, Operations Research Letters, 20, 129-139 (1997) · Zbl 0882.90069
[10] Lee, C.-Y; Cheng, T. C.E; Lin, B. M.T, Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39, 616-625 (1993) · Zbl 0783.90054
[11] Lee, C.-Y; Liman, S. D., Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29, 375-382 (1992) · Zbl 0738.68043
[12] Lee, C.-Y; Liman, S. D., Capacitated two-parallel machines scheduling to minimize sum of job completion times, Discrete Applied Mathematics, 41, 211-222 (1993) · Zbl 0778.90028
[13] Lee, C.-Y; Lei, L.; Pinedo, M., Current trend in deterministic scheduling, Annals of Operations Research, 70, 1-42 (1997)
[14] Lee, C.-Y; Vairaktarakis, G., Minimizing makespan in hybrid flowshops, Operations Research Letters, 16, 149-158 (1994) · Zbl 0812.90066
[15] Mosheiov, G., Minimizing the sum of job completion times on capacitated parallel machines, Mathematical and Computer Modelling, 20, 91-99 (1994) · Zbl 0810.90072
[16] Pinedo, M.L., 1995. Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs, NJ; Pinedo, M.L., 1995. Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs, NJ · Zbl 1145.90393
[17] Schmidt, G., Scheduling on semi-identical processors, Zeitschrift fur Operations Research, 28, 153-162 (1984) · Zbl 0551.90044
[18] Schmidt, G., Scheduling independent tasks with deadlines on semi-identical processors, Journal of Operational Research Society, 39, 271-277 (1988) · Zbl 0657.90051
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.