Single-machine scheduling with time window-dependent processing times

被引:2
|
作者
Lahlou, C
Dauzére-Pérès, S
机构
[1] Ecole Mines Nantes, IRRCyN, CNRS, UMR 6597, F-44307 Nantes, France
[2] Ecole Mines St Etienne, Gardanne, France
关键词
scheduling; one-machine; time-dependent processing time; time windows; computational complexity;
D O I
10.1057/palgrave.jors.2601931
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with timedependent processing times. Various computational complexity results are presented for the make-span criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases.
引用
收藏
页码:133 / 139
页数:7
相关论文
共 50 条
  • [31] Single-machine scheduling with deteriorating functions for job processing times
    Cheng, T. C. E.
    Lee, Wen-Chiung
    Wu, Chin-Chia
    APPLIED MATHEMATICAL MODELLING, 2010, 34 (12) : 4171 - 4178
  • [32] Single-machine scheduling with controllable processing times and learning effect
    Yin, Na
    Wang, Xiao-Yuan
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2011, 54 (5-8): : 743 - 748
  • [34] Single-Machine Scheduling Problems with Variable Processing Times and Past-Sequence-Dependent Delivery Times
    Wang, Ji-Bo
    Xue, Jing
    Cui, Bo
    Gao, Ming
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2022, 39 (02)
  • [35] Single-machine slack due-window assignment and scheduling with past-sequence-dependent delivery times and controllable job processing times
    Ji, Min
    Yao, Danli
    Ge, Jiaojiao
    Cheng, T. C. E.
    EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING, 2015, 9 (06) : 794 - 818
  • [36] Single-machine scheduling with controllable processing times and learning effect
    Na Yin
    Xiao-Yuan Wang
    The International Journal of Advanced Manufacturing Technology, 2011, 54 : 743 - 748
  • [37] Single-machine scheduling of multiple projects with controllable processing times
    Geng, Zhichao
    Yuan, Jinjiang
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 308 (03) : 1074 - 1090
  • [38] Single machine group scheduling with time dependent processing times and ready times
    Wang, Ji-Bo
    Wang, Jian-Jun
    INFORMATION SCIENCES, 2014, 275 : 226 - 231
  • [39] Single-machine scheduling time-dependent jobs with resource-dependent ready times
    Zhu, Valerie C. Y.
    Sun, Linyan
    Sun, Linhui
    Li, Xiaohong
    COMPUTERS & INDUSTRIAL ENGINEERING, 2010, 58 (01) : 84 - 87
  • [40] Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties
    Biskup, D
    Cheng, TCE
    ENGINEERING OPTIMIZATION, 1999, 31 (03) : 329 - 336