# American Institute of Mathematical Sciences

• Previous Article
Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations
• JIMO Home
• This Issue
• Next Article
Using emission functions in modeling environmentally sustainable traffic assignment policies
April  2013, 9(2): 323-339. doi: 10.3934/jimo.2013.9.323

## Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration

 1 Fundamental Science on Radioactive Geology and Exploration Technology Laboratory, East China Institute of Technology, Nanchang, Jiangxi 330013, China 2 Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China 3 School of Information Science and Engineering, Northeastern University, China 4 Graduate Institute of Business Administration, Cheng Shiu University, Kaohsiung County, Taiwan 5 Department of Statistics, Feng Chia University, Taichung, Taiwan

Received  September 2011 Revised  January 2013 Published  February 2013

In many real-life scheduling environments, the jobs deteriorate at a certain rate while waiting to be processed. This paper addresses some single-machine scheduling problems with past-sequence-dependent (p-s-d) delivery times and a linear deterioration. The p-s-d delivery time of a job is proportional to the job's waiting time. It is assumed that the deterioration process is reflected in the job processing times being an increasing function of their starting times. We consider the following objectives: the makespan, total completion time, total weighted completion time, maximum lateness, and total absolute differences in completion times. We seek the optimal schedules for the problems to minimize the makespan and total completion time. Despite that the computational complexities of the problems to minimize the total weighted completion time and maximum lateness remain open, we present heuristics and analyze their worst-case performance ratios, and show that some special cases of the problems are polynomially solvable. We also show that the optimal schedule for the problem to minimize the total absolute differences in completion times is $V$-shaped with respect to the normal job processing times.
Citation: Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
##### References:
 [1] B. Alidaee and N. K. Womer, Scheduling with time dependent processing times: Review and extensions,, Journal of the Operational Research Society, 50 (1999), 711. Google Scholar [2] A. Bachman and A. Janiak, Scheduling jobs with special type of start time dependent processing times,, Report No 34/97, (1997). Google Scholar [3] A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration,, European Journal of Operational Research, 126 (2000), 557. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar [4] A. Bachman, A. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs,, Information Processing Letters, 81 (2002), 81. doi: 10.1016/S0020-0190(01)00196-X. Google Scholar [5] A. Bachman, T. C. E. Cheng, A. Janiak and C. T. Ng, Scheduling start time dependent jobs to minimize the total weighted completion time,, Journal of the Operational Research Society, 53 (2002), 688. Google Scholar [6] A. Bachman, T. C. E. Cheng, A. Janiak and C. T. Ng, Three scheduling problems with deteriorating jobs to minimize the total completion time,, Information Processing Letters, 81 (2002), 327. doi: 10.1016/S0020-0190(01)00244-7. Google Scholar [7] D. Biskup, A state-of-the-art review on scheduling with learning effects,, European Journal of Operational Research, 188 (2008), 315. doi: 10.1016/j.ejor.2007.05.040. Google Scholar [8] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor,, Operations Research, 38 (1990), 495. Google Scholar [9] T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times,, European Journal of Operational Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar [10] T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations,, Annals of Operations Research, 98 (2000), 273. doi: 10.1023/A:1019216726076. Google Scholar [11] T. C. E. Cheng, S. J. Yang and D. L. Yang, Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity,, International Journal of Production Economics, 135 (2012), 154. Google Scholar [12] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. Google Scholar [13] S. K. Gupta, A. S. Kunnathur and K. Dandanpani, Optimal repayment policies for multiple loans,, Omega, 15 (1987), 323. Google Scholar [14] J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times,, Computers and Industrial Engineering, 14 (1988), 387. Google Scholar [15] G. H. Hardy, J. E. Littlewood and G. Polya, "Inequalities,", Cambridge University Press, (1967). Google Scholar [16] K. I.-J. Ho, J. Y.-T. Leung and W.-D. Wei, Complexity of scheduling tasks with time-dependent execution times,, Information Processing Letters, 48 (1993), 315. doi: 10.1016/0020-0190(93)90175-9. Google Scholar [17] K. Inderfurth, A. Janiak, M. Y. Kovalyov and F. Werner, Batching work and rework processes with limited deterioration of reworkables,, Computers and Operations Research, 33 (2006), 1595. Google Scholar [18] A. Janiak and M. Y. Kovalyov, Scheduling deteriorating jobs,, in, (2006), 12. Google Scholar [19] J. J. Kanet, Minimizing variation of flow time in single machine systems,, Management Science, 27 (1981), 1453. Google Scholar [20] H. Kise, T. Ibaraki and H. Mine, Performance analysis of six approximation algorithms for the onemachine maximum lateness scheduling problem with ready times,, Journal of the Operational Research Society of Japan, 22 (1979), 205. Google Scholar [21] C. Koulamas and G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent delivery times,, International Journal of Production Economics, 126 (2010), 264. Google Scholar [22] A. S. Kunnathur and S. K. Gupta, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem,, European Journal of Operational Research, 47 (1990), 56. doi: 10.1016/0377-2217(90)90089-T. Google Scholar [23] W. Luo and L. Chen, Approximation schemes for scheduling a maintenance and linear deteriorating jobs,, Journal of Industrial and Management Optimization, 8 (2012), 271. doi: 10.3934/jimo.2012.8.271. Google Scholar [24] M. M. Mazdeh, F. Zaerpour, A. Zareei and A. Hajinezhad, Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs,, Applied Mathematical Modelling, 34 (2010), 1498. doi: 10.1016/j.apm.2009.08.023. Google Scholar [25] G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine,, Computers & Industrial Engineering, 28 (1995), 869. Google Scholar [26] G. Mosheiov, $V$-shaped policies for scheduling deteriorating jobs,, Operations Research, 39 (1991), 979. doi: 10.1287/opre.39.6.979. Google Scholar [27] G. Mosheiov, Scheduling jobs under simple linear deterioration,, Computers & Operations Research, 21 (1994), 653. Google Scholar [28] G. Sahin and R. K. Ahuja, Single-machine scheduling with stepwise tardiness costs and release times,, Journal of Industrial and Management Optimization, 7 (2011), 825. doi: 10.3934/jimo.2011.7.825. Google Scholar [29] D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times,, Computers & Operations Research, 35 (2008), 2071. doi: 10.1016/j.cor.2006.10.010. Google Scholar [30] J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration,, Omega, 35 (2007), 397. Google Scholar [31] J.-B. Wang, A note on scheduling problems with learning effects and deteriorating jobs,, International Journal of Systems Science, 37 (2006), 827. doi: 10.1080/00207720600879260. Google Scholar [32] J.-B. Wang and T. C. E. Cheng, Scheduling problems with the effects of deterioration and learning,, Asia Pacific Journal of Operational Research, 24 (2007), 245. doi: 10.1142/S021759590700122X. Google Scholar [33] J.-B. Wang, X. Huang, X.-Y. Wang, N. Yin and L.-Y. Wang, Learning effect and deteriorating jobs in the single machine scheduling problems,, Applied Mathematical Modelling, 33 (2009), 3848. doi: 10.1016/j.apm.2009.01.004. Google Scholar [34] J.-B. Wang, Y. Jiang and G. Wang, Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning,, The International Journal of Advanced Manufacturing Technology, 41 (2009), 1221. Google Scholar [35] L.-Y. Wang, J.-B. Wang, W.-J. Gao, X. Huang and E.-M. Feng, Two single-machine scheduling problems with the effects of deterioration and learning,, The International Journal of Advanced Manufacturing Technology, 46 (2010), 715. Google Scholar [36] S.-J. Yang and D.-L. Yang, Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities,, Omega, 38 (2010), 528. Google Scholar [37] Y. Yin and D. Xu, Some single-machine scheduling problems with general effects of learning and deterioration,, Computers and Mathematics with Applications, 61 (2011), 100. doi: 10.1016/j.camwa.2010.10.036. Google Scholar [38] M.-J. Yao, S.-C. Chen and Y.-J. Chang, A common cycle approach for solving the economic lot and inspection scheduling problem,, Journal of Industrial and Management Optimization, 8 (2012), 141. Google Scholar [39] C. Zhao and H. Tang, A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity,, Computers and Operations Research, 39 (2012), 1300. doi: 10.1016/j.cor.2010.04.006. Google Scholar [40] C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions,, Applied Mathematical Modelling, 34 (2010), 238. doi: 10.1016/j.apm.2009.03.037. Google Scholar [41] C.-L. Zhao, Q.-L. Zhang and H.-Y. Tang, Scheduling problems under linear deterioration,, Acta Automatica Sinica, 29 (2003), 531. Google Scholar

show all references

##### References:
 [1] B. Alidaee and N. K. Womer, Scheduling with time dependent processing times: Review and extensions,, Journal of the Operational Research Society, 50 (1999), 711. Google Scholar [2] A. Bachman and A. Janiak, Scheduling jobs with special type of start time dependent processing times,, Report No 34/97, (1997). Google Scholar [3] A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration,, European Journal of Operational Research, 126 (2000), 557. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar [4] A. Bachman, A. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs,, Information Processing Letters, 81 (2002), 81. doi: 10.1016/S0020-0190(01)00196-X. Google Scholar [5] A. Bachman, T. C. E. Cheng, A. Janiak and C. T. Ng, Scheduling start time dependent jobs to minimize the total weighted completion time,, Journal of the Operational Research Society, 53 (2002), 688. Google Scholar [6] A. Bachman, T. C. E. Cheng, A. Janiak and C. T. Ng, Three scheduling problems with deteriorating jobs to minimize the total completion time,, Information Processing Letters, 81 (2002), 327. doi: 10.1016/S0020-0190(01)00244-7. Google Scholar [7] D. Biskup, A state-of-the-art review on scheduling with learning effects,, European Journal of Operational Research, 188 (2008), 315. doi: 10.1016/j.ejor.2007.05.040. Google Scholar [8] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor,, Operations Research, 38 (1990), 495. Google Scholar [9] T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times,, European Journal of Operational Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar [10] T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations,, Annals of Operations Research, 98 (2000), 273. doi: 10.1023/A:1019216726076. Google Scholar [11] T. C. E. Cheng, S. J. Yang and D. L. Yang, Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity,, International Journal of Production Economics, 135 (2012), 154. Google Scholar [12] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. Google Scholar [13] S. K. Gupta, A. S. Kunnathur and K. Dandanpani, Optimal repayment policies for multiple loans,, Omega, 15 (1987), 323. Google Scholar [14] J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times,, Computers and Industrial Engineering, 14 (1988), 387. Google Scholar [15] G. H. Hardy, J. E. Littlewood and G. Polya, "Inequalities,", Cambridge University Press, (1967). Google Scholar [16] K. I.-J. Ho, J. Y.-T. Leung and W.-D. Wei, Complexity of scheduling tasks with time-dependent execution times,, Information Processing Letters, 48 (1993), 315. doi: 10.1016/0020-0190(93)90175-9. Google Scholar [17] K. Inderfurth, A. Janiak, M. Y. Kovalyov and F. Werner, Batching work and rework processes with limited deterioration of reworkables,, Computers and Operations Research, 33 (2006), 1595. Google Scholar [18] A. Janiak and M. Y. Kovalyov, Scheduling deteriorating jobs,, in, (2006), 12. Google Scholar [19] J. J. Kanet, Minimizing variation of flow time in single machine systems,, Management Science, 27 (1981), 1453. Google Scholar [20] H. Kise, T. Ibaraki and H. Mine, Performance analysis of six approximation algorithms for the onemachine maximum lateness scheduling problem with ready times,, Journal of the Operational Research Society of Japan, 22 (1979), 205. Google Scholar [21] C. Koulamas and G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent delivery times,, International Journal of Production Economics, 126 (2010), 264. Google Scholar [22] A. S. Kunnathur and S. K. Gupta, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem,, European Journal of Operational Research, 47 (1990), 56. doi: 10.1016/0377-2217(90)90089-T. Google Scholar [23] W. Luo and L. Chen, Approximation schemes for scheduling a maintenance and linear deteriorating jobs,, Journal of Industrial and Management Optimization, 8 (2012), 271. doi: 10.3934/jimo.2012.8.271. Google Scholar [24] M. M. Mazdeh, F. Zaerpour, A. Zareei and A. Hajinezhad, Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs,, Applied Mathematical Modelling, 34 (2010), 1498. doi: 10.1016/j.apm.2009.08.023. Google Scholar [25] G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine,, Computers & Industrial Engineering, 28 (1995), 869. Google Scholar [26] G. Mosheiov, $V$-shaped policies for scheduling deteriorating jobs,, Operations Research, 39 (1991), 979. doi: 10.1287/opre.39.6.979. Google Scholar [27] G. Mosheiov, Scheduling jobs under simple linear deterioration,, Computers & Operations Research, 21 (1994), 653. Google Scholar [28] G. Sahin and R. K. Ahuja, Single-machine scheduling with stepwise tardiness costs and release times,, Journal of Industrial and Management Optimization, 7 (2011), 825. doi: 10.3934/jimo.2011.7.825. Google Scholar [29] D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times,, Computers & Operations Research, 35 (2008), 2071. doi: 10.1016/j.cor.2006.10.010. Google Scholar [30] J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration,, Omega, 35 (2007), 397. Google Scholar [31] J.-B. Wang, A note on scheduling problems with learning effects and deteriorating jobs,, International Journal of Systems Science, 37 (2006), 827. doi: 10.1080/00207720600879260. Google Scholar [32] J.-B. Wang and T. C. E. Cheng, Scheduling problems with the effects of deterioration and learning,, Asia Pacific Journal of Operational Research, 24 (2007), 245. doi: 10.1142/S021759590700122X. Google Scholar [33] J.-B. Wang, X. Huang, X.-Y. Wang, N. Yin and L.-Y. Wang, Learning effect and deteriorating jobs in the single machine scheduling problems,, Applied Mathematical Modelling, 33 (2009), 3848. doi: 10.1016/j.apm.2009.01.004. Google Scholar [34] J.-B. Wang, Y. Jiang and G. Wang, Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning,, The International Journal of Advanced Manufacturing Technology, 41 (2009), 1221. Google Scholar [35] L.-Y. Wang, J.-B. Wang, W.-J. Gao, X. Huang and E.-M. Feng, Two single-machine scheduling problems with the effects of deterioration and learning,, The International Journal of Advanced Manufacturing Technology, 46 (2010), 715. Google Scholar [36] S.-J. Yang and D.-L. Yang, Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities,, Omega, 38 (2010), 528. Google Scholar [37] Y. Yin and D. Xu, Some single-machine scheduling problems with general effects of learning and deterioration,, Computers and Mathematics with Applications, 61 (2011), 100. doi: 10.1016/j.camwa.2010.10.036. Google Scholar [38] M.-J. Yao, S.-C. Chen and Y.-J. Chang, A common cycle approach for solving the economic lot and inspection scheduling problem,, Journal of Industrial and Management Optimization, 8 (2012), 141. Google Scholar [39] C. Zhao and H. Tang, A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity,, Computers and Operations Research, 39 (2012), 1300. doi: 10.1016/j.cor.2010.04.006. Google Scholar [40] C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions,, Applied Mathematical Modelling, 34 (2010), 238. doi: 10.1016/j.apm.2009.03.037. Google Scholar [41] C.-L. Zhao, Q.-L. Zhang and H.-Y. Tang, Scheduling problems under linear deterioration,, Acta Automatica Sinica, 29 (2003), 531. Google Scholar
 [1] Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 [2] Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 [3] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [4] Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076 [5] Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 [6] Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 [7] Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 [8] Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259 [9] Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757 [10] Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 [11] Dang H. Nguyen, George Yin. Recurrence for switching diffusion with past dependent switching and countable state space. Mathematical Control & Related Fields, 2018, 8 (3&4) : 879-897. doi: 10.3934/mcrf.2018039 [12] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [13] P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95 [14] Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007 [15] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [16] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [17] Simon Brendle, Rainer Nagel. PFDE with nonautonomous past. Discrete & Continuous Dynamical Systems - A, 2002, 8 (4) : 953-966. doi: 10.3934/dcds.2002.8.953 [18] Péter Koltai, Alexander Volf. Optimizing the stable behavior of parameter-dependent dynamical systems --- maximal domains of attraction, minimal absorption times. Journal of Computational Dynamics, 2014, 1 (2) : 339-356. doi: 10.3934/jcd.2014.1.339 [19] Sabine Wittevrongel, Bart Feyaerts, Herwig Bruneel, Stijn De Vuyst. Delay characteristics in place-reservation queues with class-dependent service times. Journal of Industrial & Management Optimization, 2019, 15 (1) : 37-58. doi: 10.3934/jimo.2018031 [20] Madhu Jain, Sudeep Singh Sanga. Admission control for finite capacity queueing model with general retrial times and state-dependent rates. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-25. doi: 10.3934/jimo.2019073

2018 Impact Factor: 1.025

## Metrics

• HTML views (0)
• Cited by (12)

• on AIMS