Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect

被引：0
作者：
Radosław Rudek
机构：
[1] Wrocław University of Economics,
来源：
The International Journal of Advanced Manufacturing Technology | 2012年 / 59卷
关键词：
Scheduling; Deteriorating; Aging effect; Computational complexity; Polynomial algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we analyze some single machine scheduling problems with the aging effect. We extend the sum-of-processing-time-based aging model such that the fatigue caused by each job to the machine is equal to a non-increasing function dependent on the normal processing time of a job and the aging effect is job dependent. Although the proposed model is more general and describes more precisely the real-life settings, we show that the special cases of the maximum completion time and the maximum lateness minimization problems with this model are still polynomially solvable. However, we prove the maximum completion time minimization problem with the sum-of-processing-time-based aging model is strongly NP-hard if some jobs have deadlines and constant processing times. On this basis, we show that the maximum lateness minimization problem with this aging model is also strongly NP-hard.
引用
收藏
页码：299 / 309
页数：10
相关论文
共 67 条
  • [1] Chang PC(2009)A note on due-date assignment and single machine scheduling with a learning/aging effect Int J Prod Econ 117 142-149
  • [2] Chen SH(2004)A concise survey of scheduling with time-dependent processing times Eur J Oper Res 152 1-13
  • [3] Mani V(2010)Single-machine scheduling with deteriorating functions for job processing times Appl Math Model 34 4171-4178
  • [4] Cheng TCE(2001)Impact of added rest breaks on the productivity and well being of workers Ergonomics 44 164-174
  • [5] Ding Q(1964)On a mechanistic approach to fatigue and rest periods Int J Prod Res 3 327-332
  • [6] Lin BMT(1996)A note on scheduling on a single processor with speed dependent on a number of executed jobs Inf Process Lett 57 297-300
  • [7] Cheng TCE(2008)Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation J Sched 11 357-370
  • [8] Lee WC(1979)Optimization and approximation in deterministic sequencing and scheduling: a survey Ann Discrete Math 5 287-326
  • [9] Wu CC(2010)Scheduling jobs under an aging effect J Oper Res Soc 61 1041-1048
  • [10] Dababneh AJ(2008)Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect J Oper Res Soc 59 416-420
1234567