# American Institute of Mathematical Sciences

• Previous Article
Using emission functions in modeling environmentally sustainable traffic assignment policies
• JIMO Home
• This Issue
• Next Article
Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations
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 and 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-729. [2] A. Bachman and A. Janiak, Scheduling jobs with special type of start time dependent processing times, Report No 34/97, Institute of Engineering Cybernetics, Wroclaw University of Technology, 1997. [3] A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0. [4] A. Bachman, A. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81 (2002), 81-84. doi: 10.1016/S0020-0190(01)00196-X. [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-693. [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-333. doi: 10.1016/S0020-0190(01)00244-7. [7] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329. doi: 10.1016/j.ejor.2007.05.040. [8] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. [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-13. doi: 10.1016/S0377-2217(02)00909-8. [10] T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations, Annals of Operations Research, 98 (2000), 273-290. doi: 10.1023/A:1019216726076. [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-161. [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-326. [13] S. K. Gupta, A. S. Kunnathur and K. Dandanpani, Optimal repayment policies for multiple loans, Omega, 15 (1987), 323-330. [14] J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1988), 387-393. [15] G. H. Hardy, J. E. Littlewood and G. Polya, "Inequalities," Cambridge University Press, London, 1967. [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-320. doi: 10.1016/0020-0190(93)90175-9. [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-1605. [18] A. Janiak and M. Y. Kovalyov, Scheduling deteriorating jobs, in "Scheduling in Computer and Manufacturing Systems" (ed. A. Janiak), Warszawa, WKL, (2006), 12-25. [19] J. J. Kanet, Minimizing variation of flow time in single machine systems, Management Science, 27 (1981), 1453-1459. [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-224. [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-266. [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-64. doi: 10.1016/0377-2217(90)90089-T. [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-283. doi: 10.3934/jimo.2012.8.271. [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-1510. doi: 10.1016/j.apm.2009.08.023. [25] G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine, Computers & Industrial Engineering, 28 (1995), 869-879. [26] G. Mosheiov, $V$-shaped policies for scheduling deteriorating jobs, Operations Research, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979. [27] G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers & Operations Research, 21 (1994), 653-659. [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-848. doi: 10.3934/jimo.2011.7.825. [29] D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers & Operations Research, 35 (2008), 2071-2078. doi: 10.1016/j.cor.2006.10.010. [30] J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402. [31] J.-B. Wang, A note on scheduling problems with learning effects and deteriorating jobs, International Journal of Systems Science, 37 (2006), 827-832. doi: 10.1080/00207720600879260. [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-261. doi: 10.1142/S021759590700122X. [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-3853. doi: 10.1016/j.apm.2009.01.004. [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-1226. [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-720. [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-533. [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-108. doi: 10.1016/j.camwa.2010.10.036. [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-162. [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-1303. doi: 10.1016/j.cor.2010.04.006. [40] C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34 (2010), 238-243. doi: 10.1016/j.apm.2009.03.037. [41] C.-L. Zhao, Q.-L. Zhang and H.-Y. Tang, Scheduling problems under linear deterioration, Acta Automatica Sinica, 29 (2003), 531-535.

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-729. [2] A. Bachman and A. Janiak, Scheduling jobs with special type of start time dependent processing times, Report No 34/97, Institute of Engineering Cybernetics, Wroclaw University of Technology, 1997. [3] A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0. [4] A. Bachman, A. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81 (2002), 81-84. doi: 10.1016/S0020-0190(01)00196-X. [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-693. [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-333. doi: 10.1016/S0020-0190(01)00244-7. [7] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329. doi: 10.1016/j.ejor.2007.05.040. [8] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. [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-13. doi: 10.1016/S0377-2217(02)00909-8. [10] T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations, Annals of Operations Research, 98 (2000), 273-290. doi: 10.1023/A:1019216726076. [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-161. [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-326. [13] S. K. Gupta, A. S. Kunnathur and K. Dandanpani, Optimal repayment policies for multiple loans, Omega, 15 (1987), 323-330. [14] J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1988), 387-393. [15] G. H. Hardy, J. E. Littlewood and G. Polya, "Inequalities," Cambridge University Press, London, 1967. [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-320. doi: 10.1016/0020-0190(93)90175-9. [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-1605. [18] A. Janiak and M. Y. Kovalyov, Scheduling deteriorating jobs, in "Scheduling in Computer and Manufacturing Systems" (ed. A. Janiak), Warszawa, WKL, (2006), 12-25. [19] J. J. Kanet, Minimizing variation of flow time in single machine systems, Management Science, 27 (1981), 1453-1459. [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-224. [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-266. [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-64. doi: 10.1016/0377-2217(90)90089-T. [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-283. doi: 10.3934/jimo.2012.8.271. [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-1510. doi: 10.1016/j.apm.2009.08.023. [25] G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine, Computers & Industrial Engineering, 28 (1995), 869-879. [26] G. Mosheiov, $V$-shaped policies for scheduling deteriorating jobs, Operations Research, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979. [27] G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers & Operations Research, 21 (1994), 653-659. [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-848. doi: 10.3934/jimo.2011.7.825. [29] D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers & Operations Research, 35 (2008), 2071-2078. doi: 10.1016/j.cor.2006.10.010. [30] J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402. [31] J.-B. Wang, A note on scheduling problems with learning effects and deteriorating jobs, International Journal of Systems Science, 37 (2006), 827-832. doi: 10.1080/00207720600879260. [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-261. doi: 10.1142/S021759590700122X. [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-3853. doi: 10.1016/j.apm.2009.01.004. [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-1226. [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-720. [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-533. [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-108. doi: 10.1016/j.camwa.2010.10.036. [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-162. [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-1303. doi: 10.1016/j.cor.2010.04.006. [40] C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34 (2010), 238-243. doi: 10.1016/j.apm.2009.03.037. [41] C.-L. Zhao, Q.-L. Zhang and H.-Y. Tang, Scheduling problems under linear deterioration, Acta Automatica Sinica, 29 (2003), 531-535.
 [1] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 [2] Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066 [3] Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190 [4] 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 and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 [5] Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124 [6] 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 and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 [7] 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 and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 [8] 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 and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [9] Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076 [10] Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259 [11] 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 and Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 [12] 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 and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 [13] Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142 [14] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2567-2578. doi: 10.3934/jimo.2021081 [15] Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 [16] Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757 [17] Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008 [18] Dang H. Nguyen, George Yin. Recurrence for switching diffusion with past dependent switching and countable state space. Mathematical Control and Related Fields, 2018, 8 (3&4) : 879-897. doi: 10.3934/mcrf.2018039 [19] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [20] P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

2021 Impact Factor: 1.411