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

Yunqiang Yin; T. C. E. Cheng; Jianyou Xu; Shuenn-Ren Cheng; Chin-Chia Wu

doi:10.3934/jimo.2013.9.323

Article Contents

2013, Volume 9, Issue 2: 323-339. Doi: 10.3934/jimo.2013.9.323

This issue Previous Article Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations Next Article Using emission functions in modeling environmentally sustainable traffic assignment policies

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
2.
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
3.
School of Information Science and Engineering, Northeastern University
4.
Graduate Institute of Business Administration, Cheng Shiu University, Kaohsiung County
5.
Department of Statistics, Feng Chia University, Taichung

Received: August 31, 2011

Revised: December 31, 2012

Published: March 2013

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90B3E; Secondary: 90C59.

Citation:

Related Papers

Cited by

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.