Study of Scheduling Problems with Machine Availability Constraint

Document Type: Research Paper

Authors

1 Young Researchers Club, Tehran’s Science and Research Branch, Islamic Azad University, Tehran, Iran

2 Faculty of Accounting and Management, Allameh Tabataba’i University, Tehran, Iran

Abstract

In real world scheduling applications, machines might not be available during certain time periods due to deterministic or stochastic causes. In this article, the machine scheduling with availability constraints for both deterministic and stochastic cases with different environments, constraints and performance measures will be discussed. The existing body of research work in the literature will be completely reviewed and the NP-complete models will be identified.

Keywords

Main Subjects


[1] Adiri I., Bruno J., Frostig E., Rinnooy Kan A.H.G. (1989), Single machine flow-time scheduling
with a single breakdown; Acta Informatica 26; 679-696.
[2] Aggoune R. (2002), Ordonnancement d’Ateliers sous Contraintes de Disponibilité des Machines;
Ph.D. Thesis, Universite de Metz; France.
[3] Aggoune R. (2004a), Two-Job Shop Scheduling Problems with Availability Constraints. In:
Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling
(ICAPS 2004), Whistler (Canada).
[4] Aggoune R. (2004b), Minimizing the makespan for the flow shop scheduling problem with
availability constraints; European Journal of Operational Research 153; 534-543.
[5] Aggoune R., Portmann M.-C. (2006), Flow shop scheduling problem with limited machine
availability: A heuristic approach; International Journal of Production Economics 99; 4-15.
[6] Albers S., Schmidt G. (1999), Scheduling with Unexpected Machine Breakdowns. In: Computer
Science; Vol. 1671, Proceedings of the Third International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial
Algorithms and Techniques, Springer-Verlag: London, 269-280.
[7] Albers S., Schmidt G. (2001), Scheduling with unexpected machine breakdowns; Discrete Applied
Mathematics 110(2-3); 85-99.
[8] Albers S., Schmidt G. (2004), Scheduling with Unexpected Machine Breakdowns; In:
Randomization, Approximation, and Combinatorial Optimization (Algorithms and Techniques),
Springer: Berlin/ Heidelberg, Volume 1671; 269-280.
[9] Allahverdi A. (1995), Two-stage Production Scheduling with Separated Set-up Times and Stochastic
Breakdowns; Journal of the Operational Research Society 46(7); 896-904.
[10] Allahverdi A. (1996), Two-machine proportionate flowshop scheduling with breakdowns to
minimize maximum lateness; Computers & Operations Research 23; 909-916.
[11] Allahverdi A. (1997), Scheduling in stochastic flowshops with independent setup, processing and
removal times; Computers and Operations Research 24(10); 955-960.
[12] Allahverdi A., Mittenthal J. (1998), Dual criteria scheduling on a two-machine flowshop subject to
random breakdowns; International Transactions in Operational Research 5; 317-324.
[13] Allaoui H., Artiba A. (2006), Scheduling two-stage hybrid flow shop with availability constraints;
Computers and Operations Research 33(5); 1399-1419.
[14] Apon A., Wilbur L. (2003), AmpNet - a highly available cluster interconnection network;
Proceedings IEEE International Symposium on Parallel and Distributed Processing.
[15] Balas E., Lancia G., Serafini P., Vazacopoulos A. (1998), Job shop scheduling with deadlines;
Journal of Combinatorial Optimization 1(4); 329-353.
[16] Birge J., Frenk J.B.G., Mittenthal J., Rinnooy Kan A.H.G. (1990), Single machine scheduling subject
to stochastic breakdowns; Naval Research Logistics 37; 661-677.

[17] Birge J., Glazebrook K.D. (1988), Assessing the effects of machine breakdowns in stochastic
scheduling; Operations Research Letters 7(6); 267- 271.
[18] Blazewicz J., Breit J., Formanowicz P., Kubiak W., Schmidt G. (2001), Heuristic algorithms for the
two-machine flowshop problem with limited machine availability; Omega Journal 29; 599-608.
[19] Blazewicz J., Dell'Olmo P., Drozdowski M., Maczka P. (2003), Scheduling multiprocessor tasks on
parallel processors with limited availability; European Journal of Operational Research 149; 377-
389.
[20] Blażewicz J., Drozdowski M., Formanowicz P., Kubiak W., Schmidt G. (2000), Scheduling
preemtable tasks on parallel processors with limited availability; Parallel Computing 26(9); 1195-
1211.
[21] Blażewicz J., Ecker K., Pesch E., Schmidt G., Węglarz J. (1996), Scheduling Computer and
Manufacturing Processes; Springer; Berlin.
[22] Braun O., Lai T.-C., Schmidt G., Sotskov Y.N. (2002), Stability of Johnson’s schedule with respect
to limited machine availability; International Journal of Production Research 40(17); 4381-4400.
[23] Breit J. (2004), An improved approximation algorithm for two-machine flow shop scheduling with
an availability constraint; Information Processing Letters 90 (6); 273-278.
[24] Breit J., Schmidt G., Strusevich V.A. (2001a), Two-machine open shop scheduling with an
availability constraint; Operations Research Letters 29(2); 65-77.
[25] Brucker P., Garey M.R., Johnson D.S. (1977), Scheduling equal-length tasks under treelike
precedence constraints to minimize maximum lateness; Mathematics of Operations Research 2; 275-
284.
[26] Cai X., Wu X., Zhou X. (2005), Dynamically optimal policies for stochastic scheduling subject to
preemptive-repeat machine breakdowns; IEEE Transactions on Automation Science and Engineering
2(2); 158-172.
[27] Canon C., Billaut J.-C., Bouquard J.-L. (2003), The one-machine sequencing problem with
availability constraints; Technical Report 271, Laboratoire d’Informatique de Universitè de Tours;
Tours (France).
[28] Carlier J. (1982), The one-machine sequencing problem; European Journal of Operational Research
11; 42-47.
[29] Chan F.T.S., Wong T.C., Chan L.Y. (2006), Flexible job-shop scheduling problem under resource
constraints; International Journal of Production Research 44(11); 2071-2089.
[30] Chen W.J. (2007), Scheduling of jobs and maintenance in a textile company; International Journal
of Advanced Manufacturing Technology 31; 737-742.
[31] Cheng T.C.E., Liu Z. (2003a), Approximability of two-machine no-wait flowshop scheduling with
availability constraints; Operations Research Letters 31; 319-322.
[32] Cheng T.C.E., Liu Z. (2003b), 3/2-approximation for two-machine no-wait flowshop scheduling
with availability constraints; Information Processing Letters 88; 161-165.
[33] Cheng T.C.E., Wang G. (1999), Two-machine flowshop scheduling with consecutive availability
constraints; Information Processing Letters 71(2); 49-54.

[34] Cheng T.C.E., Wang G. (2000), An improved heuristic for two-machine flowshop scheduling with
an availability constraint; Operations Research Letters 26; 223-229.
[35] Dehnar Saidy H.R., Taghavi-Fard M.T. (2008), Flexible Job Shop Scheduling Under Availability
Constraints; Journal of Industrial Engineering International; In press.
[36] Dolev D., Warmuth M.K. (1985a), Scheduling flat graphs; SIAM Journal on Computing 14; 638-
657.
[37] Dolev D., Warmuth M.K. (1985b), Profile scheduling of opposing forests and level orders. SIAM
Journal on Algebraic and Discrete Methods 6; 665-687.
[38] Espinouse M.L., Formanowicz P., Penz B. (1999), Minimizing the makespan in the two-machine nowait
flow-shop with limited machine availability; Computer and Industrial Engineering 37; 497-500.
[39] Garey M.R., Johnson D.S. (1977), Two-processor scheduling with start-times and deadlines, SIAM
Journal on Computing 6; 416-426.
[40] Gawiejnowicz S. (2007), Scheduling deteriorating jobs subject to job or machine availability
constraints; European Journal of Operational Research 180; 472–478.
[41] Glazebrook K.D. (1987), Evaluating the effects of machine breakdowns in stochastic scheduling
problems; Naval Research Logistics 34; 319-335.
[42] Graham R.L. (1969), Bounds on multiprocessing timing anomalies; SIAM Journal on Applied
Mathematics 17; 263-269.
[43] Johnson S.M. (1954), Optimal Two and Three Stage Production Schedules with Setup Times
Included; Naval Research Logistics Quarterly 1(1); 61- 68.
[44] Jungwattanakit J., Reodecha M., Chaowalitwongse P., Werner F. (2008), Algorithms for Flexible
Flow Shop Problems with Unrelated Parallel Machines, Setup Times, and Dual Criteria;
International Journal of Advanced Manufacturing Technology (in press); DOI 10.1007/s00170-007-
0977-0.
[45] Kaspi M., Montreuil B. (1988), On the scheduling of identical parallel processes with arbitrary initial
processor available time; Research Report, School of Industrial Engineering; Purdue University.
[46] Kellerer H. (1998), Algorithms for multiprocessor scheduling with machine release time; IIE
Transactions 30(11); 991-999.
[47] Kubiak W., Blażewicz J., Formanowicz P., Breit J., Schmidt G. (2002), Two-machine flow shops
with limited machine availability; European Journal of Operational Research 136(3); 528-540.
[48] Kubiak W., Blażewicz J., Formanowicz P., Schmidt G. (1997), A branch and bound algorithm for
two machine flow shop with limited machine availability; The Abstracts of the Tenth Meeting of the
European Chapter on Combinatorial Optimization 38.
[49] Kubzin M.A., Strusevich V.A., Breit J., Schmidt G. (2005), Polynomial-time approximation schemes
for two-machine open shop scheduling with nonavailability constraints; Naval Research Logistics
53(1); 16-23.
[50] Lau H. C., Zhang C. (2004), Job Scheduling with Unfixed Availability Constraints; Proceeding of
35th Meeting of the Decision Sciences Institute (DSI), Boston (USA), 4401-4406.

[51] Lawler E.L., Martel C.U. (1989), Preemptive scheduling of two uniform machines to minimize the
number of late jobs; Operations Research 37; 314-318.
[52] Leangsuksun C., Tikotekar A., Pourzandi M., Haddad I. (2005), Feasibility study and early
experimental results towards cluster survivability; Proceedings of the IEEE International Symposium
on Cluster Computing and the Grid, 77-81.
[53] Lee C. Y. (1991), Parallel machine scheduling with nonsimultaneous machine available time;
Discrete Applied Mathematics 30; 53-61.
[54] Lee C. Y. (1996), Machine scheduling with an availability constraint; Journal of Global
Optimization 9; 395-416.
[55] Lee C. Y. (1997), Minimizing the makespan in two-machine flowshop scheduling problem with an
availability constraint; Operations Research Letters 20; 129-139.
[56] Lee C. Y. (1999), Two-machine flowshop scheduling with availability constraints; European Journal
of Operational Research 114; 420-429.
[57] Lee C. Y., Lei L., Pinedo M. (1997), Current trends in deterministic scheduling; Annals of operations
Research 70; 1-41.
[58] Lee C. Y., Liman S.D. (1992), Single machine flow-time scheduling with scheduled maintenance;
Acta Informatica 29; 375-382.
[59] Lee C. Y., Liman S.D. (1993), Capacitated two-parallel machines scheduling to minimize sum of job
completion times; Discrete Applied Mathematics 41; 211-222.
[60] Lee C. Y., Lin C.S. (2001), Single-machine scheduling with maintenance and repair rate-modifying
activities; European Journal of Operational Research 135; 493-513.
[61] Leon V. J., Wu S. D. (1992), On scheduling with ready-times, due-dates and vacations; Naval
Research Logistics 39; 53-65.
[62] Levitin G. (2000), Multistate Series-Parallel System Expansion-Scheduling Subject to Availability
Constraints; IEEE Transactions on Reliability 49(1); 71-79.
[63] Li W., Cao J. (1995), Stochastic scheduling on a single machine subject to multiple breakdowns
according to different probabilities; Operations Research Letters 18; 81-91.
[64] Lin G.H., Yao E.Y., He Y. (1998), Parallel machine scheduling to maximize the minimum load with
nonsimultaneous machine available times; Operations Research Letters 22; 75-81.
[65] Liu Z., Sanlaville E. (1995a), Preemptive scheduling with variable profile, precedence constraints
and due dates; Discrete Applied Mathematics 58; 253-280.
[66] Liu Z., Sanlaville E. (1995b), Profile scheduling of list algorithms. In: Chretienne, P. et al. (Ed),
Scheduling Theory and its Applications, John Wiley & Sons: New York, 91-110.
[67] Lorigeon T., Billaut J. C., Bouquard J. L. (2002), A dynamic programming algorithm for scheduling
jobs in a two-machine open shop with an availability constraint; Journal of the Operational Research
Society 53 (11); 1239-124.

[68] Mauguière P., Billaut J. C., Bouquard J. L. (2003a), Scheduling resumable and non-resumable
operations; In: Proceedings of the Joint International Meeting EURO/INFORMS, Istanbul (Turkey),
166-167.
[69] Mauguière P., Bouquard J. L., Billaut J. C. (2003b), A branch and bound algorithm for a job shop
scheduling problem with availability constraints; In: Proceedings of the Sixth Workshop on Models
and Algorithms for Planning and Scheduling Problems, MAPSP’2003, Aussois (France), 147-148.
[70] Mauguière P., Billaut J. C., Bouquard J. L. (2005), New single machine and job shop scheduling
problems with availability constraints; Journal of Scheduling 8; 211-231.
[71] McNaughton R. (1959), Scheduling with deadlines and loss functions, Management Science 6; 1-12.
[72] Moore J.M. (1968), An n job, one machine sequencing algorithm for minimizing the number of late
jobs; Management Science 15; 102-109.
[73] Mosheiov G. (1994), Minimizing the sum of job completion times on capacitated parallel machines;
Mathematical and Computer Modelling 20; 91-99.
[74] Ng C.T., Kovalyov M.Y. (2003), An FPTAS for scheduling a two-machine flowshop with one
unavailability interval; Naval Research Logistics 51(3); 307-315.
[75] Papadimitriou C.H., Yanakakis M. (1979), Scheduling interval ordered tasks; SIAM Journal on
Computing 8; 405-409.
[76] Pinedo M. (2001), Scheduling: Theory, Algorithms and Systems; 2nd edition, Prentice-Hall;
Englewood Cliffs, NJ.
[77] Sanlaville E. (1995), Nearly on line scheduling of preemptive independent tasks; Discrete Applied
Mathematics 57; 229-241.
[78] Sanlaville E., Schmidt G. (1998), Machine scheduling with availability constraints; Acta Informatica
35; 795-811.
[79] Schmidt G. (1984), Scheduling on semi-identical processors; Zeitschrift für Operations Research
A28; 153-162.
[80] Schmidt G. (1988), Scheduling independent tasks with deadlines on semi-identical processors;
Journal of Operational Research Society 39; 271-277.
[81] Schmidt G. (2000a), Performance guarantee of two simple priority rules for production scheduling;
International Journal of Production Economics 68(2); 151-159.
[82] Schmidt G. (2000b), Scheduling with limited machine availability; European Journal of Operational
Research 121; 1-15.
[83] Schopf J.M., Berman F. (1999), Stochastic Scheduling; Proceedings of the ACM/IEEE Conference
Supercomputing. Portland-Oregon (United States of America).
[84] Sheen G. J., Liao L. W. (2007), Scheduling machine-dependent jobs to minimize lateness on
machines with identical speed under availability constraints; Computers & Operations Research
34(8); 2266-2278.
[85] Ullman J.D. (1975), NP-complete scheduling problems; Journal of Computer and System Sciences
10; 384-393.

[86] Wang G., Cheng T.C.E. (2001), Heuristics for two-machine no-wait flowshop scheduling with an
availability constraint; Information Processing Letters 80; 305-309.
[87] Wang X., Cheng T.C.E. (2006), Machine scheduling with an availability constraint and job delivery
coordination; Naval Research Logistics 54(1); 11-20.
[88] Wang X., Cheng T.C.E. (2007a), Heuristics for two-machine flowshop scheduling with setup times
and an availability constraint; Computers & Operations Research 34; 152-162.
[89] Wang X., Cheng T.C.E. (2007b), An approximation scheme for two-machine flowshop scheduling
with setup times and an availability constraint; Computers and Operations Research 34(10); 2894-
2901.
[90] Wu C.C., Lee W.C. (2003), Scheduling linear deteriorating jobs to minimize makespan with an
availability constraint on a single machine; Information Processing Letters 87 (2); 89–93.
[91] Xie T., Qin X. (2006), Stochastic Scheduling with Availability Constraints in Heterogeneous
Clusters; Proceedings of the 8th IEEE International Conference on Cluster Computing (Cluster 2006
IEEE), 1-10.
[92] Yoshida T., Hitomi K. (1979), Optimal two-stage production scheduling with setup times separated;
AIIE Transactions 11; 261–263.
[93] Breit J., Schmidt G., Strusevich V.A., “Non-preemptive two-machine open shop scheduling with
non-availability constraints”, Selected Research Papers/ Abstracts, Source: Mathematical Methods of
Operation Research 57; http://www.itm.uni-sb.de/staff/gs/abstracts.htm, June 2001b.
[94] Türkcan A., “Machine Scheduling with Availability Constraints”,
http://citeseer.ist.psu.edu/turkcan99machine.html, April 15 1999.