• 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 & 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]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[2]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

[3]

Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1779-1799. doi: 10.3934/dcdss.2020454

[4]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[5]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

[6]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[7]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (75)
  • HTML views (0)
  • Cited by (14)

[Back to Top]