Abstract
This paper is concerned with two-machine no-wait flow shop scheduling problems in which the actual processing time of each job is a proportional function of its starting time and each machine may have non-availability intervals. The objective is to minimize the makespan. We assume that the non-availability intervals are imposed on only one machine. Moreover, the number of non-availability intervals, the start time and end time of each interval are known in advance. We show that the problem with a single non-availability interval is NP-hard in the ordinary sense and the problem with an arbitrary number of non-availability intervals is NP-hard in the strong sense.
Article PDF
Avoid common mistakes on your manuscript.
References
Alidaee B., Womer N.K.: Scheduling with time dependent processing times: review and extensions. J. Oper. Res. Soc. 50, 711–720 (1999)
Browne S., Yechiali U.: Scheduling deteriorating jobs on a single processor. Oper. Res. 38, 495–498 (1990)
Cheng T.C.E., Ding Q., Lin B.M.T.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152, 1–13 (2004)
Cheng T.C.E., Liu Z.: Approximability of two-machine no-wait flow shop scheduling with availability constraints. Oper. Res. Lett. 31, 319–322 (2003)
Espinouse M.L., Formanovicz P., Penz B.: Complexity results and approximation algorithms for the two-machine no-wait flow shop with limited machine availability. J. Oper. Res. Soc. 52, 116–121 (2001)
Floudas, C.A., Pardalos, P.M. (eds): Encyclopedia of Optimization, 2nd edn. Springer, Berlin (2009)
Gawiejnowicz S.: Scheduling deteriorating jobs subject to job or machine availability constraints. Eur. J. Oper. Res. 180, 472–478 (2007)
Gawiejnowicz S.: Time-Dependent Scheduling. Springer-Verlag, Berlin (2008)
Hsu, C.-J., Yang, S.-J., Yang, D.-L.: Due-date assignment and optional maintenance activity scheduling problem with linear deteriorating jobs. J. Mar. Sci. Technol. (2010, in press)
Ji M., He Y., Cheng T.C.E.: Scheduling linear deteriorating jobs with availability constraint on a single machine. Theor. Comput. Sci. 362, 115–126 (2006)
Johnson D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 2, 393–405 (1982)
Kononov A., Gawiejnowicz S.: NP-hard cases in scheduling deteriorating jobs on dedicated machines. J. Oper. Res. Soc. 52, 708–717 (2001)
Lee C.-Y.: Minimizing the makespan in the two-machine flow shop scheduling problem with an availability constraint. Oper. Res. Lett. 20, 129–139 (1997)
Mosheiov G.: Scheduling jobs under simple linear deterioration. Comput. Oper. Res. 21, 653–659 (1994)
Mosheiov G.: Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Appl. Math. 117, 195–209 (2002)
Pardalos, P.M., Resende, M.G.C. (eds.): Handbook of Applied Optimization. Oxford University Press (2002)
Wang G., Cheng T.C.E.: Heuristics for two-machine no-wait flow shop scheduling with an availability constraints. Inf. Process. Lett. 80, 305–309 (2001)
Wu C.-C., Lee W.-C.: Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine. Inf. Process. Lett. 87, 89–93 (2003)
Yang S.-J., Yang D.-L., Cheng T.C.E.: Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. Comput. Oper. Res. 37, 1510–1514 (2010)
Yang, S.-J., Yang, D.-L.: Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega Int. J. Manag. Sci. (2010). doi:10.1016/j.omega.2010.01.003
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhao, C., Tang, H. A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim Lett 5, 183–190 (2011). https://doi.org/10.1007/s11590-010-0202-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0202-1