No Access

Scheduling Deteriorating Jobs with Availability Constraints to Minimize the Makespan

School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning 110034, People’s Republic of China

E-mail Address: zhaochuanli@synu.edu.cn

Corresponding author.

Search for more papers by this author

and

Hengyong Tang

School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning 110034, People’s Republic of China

E-mail Address: hytang43876@sina.com

Search for more papers by this author

https://doi.org/10.1142/S0217595916500482Cited by:0 (Source: Crossref)

Abstract

In this paper, we consider the scheduling problem in which the processing time of a job is a linear increasing function of its starting time and machine with availability constraints. The objective is to minimize the makespan. We first present a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then show that there exists no polynomial time approximation algorithm with a constant worst-case bound for the case with two identical machines unless $P = NP$ $P = NP$ .

Keywords:

References

Alidaee, B and NK Womer (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society, 50, 711–720. Crossref, Web of Science, Google Scholar
Bosio, A and G Righini (2009). A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times. Mathematical Methods of Operations Research, 69, 271–280. Crossref, Web of Science, Google Scholar
Browne, S and U Yechiali (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495–498. Crossref, Web of Science, Google Scholar
Cheng, TCE, Q Ding, and BMT Lin (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13. Crossref, Web of Science, Google Scholar
Cheng, TCE, C-C Wu, J-C Chen, W-H Wu, and S-R Cheng, (2012). Two-machine flowshop scheduling with a truncated learning function to minimize the makespan. International Journal of Production Economics, doi: 10.1016/j.ijpe.2012.03.027. Web of Science, Google Scholar
Garey, MR and DS Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York. Google Scholar
Gawiejnowicz, S (2007). Scheduling deteriorating jobs subject to job or machine availability constraints. European Journal of Operational Research, 180, 472–478. Crossref, Web of Science, Google Scholar
Gawiejnowicz, S (2008). Time-Dependent Scheduling. Springer-Verlag, Berlin, Heidelberg. Crossref, Google Scholar
Gupta, JND and SK Gupta (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14, 387–393. Crossref, Web of Science, Google Scholar
Ji, M, Y He and TCE Cheng (2006). Scheduling linear deteriorating jobs with availability constraint on a single machine. Theoretical Computer Science, 362, 115–126. Crossref, Web of Science, Google Scholar
Kovalyov, MY and W Kubiak (1998). A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 287–297. Crossref, Google Scholar
Kovalyov, MY and W Kubiak (1999). A fully polynomial approximation scheme for the weighted earliness-tardiness problem. Operations Research, 47, 757–761. Crossref, Web of Science, Google Scholar
Lee, CY (1996). Machine scheduling with an availability constraints. Journal of Global Optimization, 9, 363–382. Crossref, Web of Science, Google Scholar
Li, D-C, P-H Hsu, C-C Wu and TCE Cheng (2011). Two-machine flowshop scheduling with truncated learning to minimize the total completion time. Computers & Industrial Engineering, 61, 655–662. Crossref, Web of Science, Google Scholar
Li S-S (2011). Scheduling proportionally deteriorating jobs in two-machine open shop with a non-bottleneck machine. Asia-Pacific Journal of Operational Research, 28, 623–631. Link, Web of Science, Google Scholar
Ma, Y, CB Chu and CR Zuo (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58, 199–211. Crossref, Web of Science, Google Scholar
Mosheiov, G (1994). Scheduling jobs under simple linear deterioration. Computers & Operations Research, 21, 653–659. Crossref, Web of Science, Google Scholar
Ng, CT, MS Barketau, TCE Cheng and MY Kovalyov (2010). “Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation. European Journal of Operational Research, 207, 601–604. Crossref, Web of Science, Google Scholar
Schuurman, P and GJ Woeginger (2011). Approximation Schemes-A Tutorial. In: Mohring, RH, CN Potts, AS Schulz, GJ Woeginger and LA Wolsey (eds.). Lectures on Scheduling to appear around 2011 A.D. Google Scholar
Tanaev, VS, VS Gordon and YM Shafransky (1994). Scheduling Theory: Single-stage Systems. Kluwer Academic Publishers. Google Scholar
Wu, CC and WC Lee (2003). Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine. Information Processing Letters, 87, 89–93. Crossref, Web of Science, Google Scholar
Wu, C-C, WH Wu, P-H Hsu and K. Lai (2011). A two-machine flowshop scheduling problem with a truncated sum of processing-times- based learning function. Applied Mathematical Modelling, doi: 10.1016/j.apm. 2011.038. Web of Science, Google Scholar
Wu, CC, WC Lee and YR Shiau (2011). A single-machine deteriorating job scheduling problem with a non-regular criterion. Asia-Pacific Journal of Operational Research, 28, 349–359. Link, Web of Science, Google Scholar
Wu, C-C, Y Yin and S-R Cheng (2012). Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions, Journal of the Operation Research Society, 1–10. Web of Science, Google Scholar
Yin, Y, CC Wu, WH Wu and S-R Cheng (2012). The single-machine total weighted tardiness scheduling problem with learning effects, Computers & Operations Research, 39, 1109–1116. Crossref, Web of Science, Google Scholar
Zhao, C-L and H-Y Tang (2011). Single machine scheduling with linear deteriorating jobs under predictive disruption. Asia-Pacific Journal of Operational Research, 28, 419–429. Link, Web of Science, Google Scholar