SCHEDULING PROPORTIONALLY DETERIORATING JOBS IN TWO-MACHINE OPEN SHOP WITH A NON-BOTTLENECK MACHINE

被引：7
作者：
Li, Shisheng [1 ]
机构：
[1] Zhengzhou Univ, Dept Math, Zhengzhou 450001, Henan, Peoples R China
来源：
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2011年 / 28卷 / 05期
关键词：
Scheduling; deteriorating jobs; open shop; non-bottleneck machine; FPTAS; DEPENDENT PROCESSING TIMES; MINIMIZE;
D O I：
10.1142/S0217595911003478
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We address the problem of scheduling proportionally deteriorating jobs in two-machine open shop in which one of the machines is non-bottleneck. The objective is to minimize the makespan. We show that the decision version of the problem is NP-complete in the ordinary sense, and present for it a fully polynomial-time approximation scheme.
引用
收藏
页码：623 / 631
页数：9
相关论文
共 50 条
  • [41] An efficient tabu search approach for the two-machine preemptive open shop scheduling problem
    Liaw, CF
    COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (14) : 2081 - 2095
  • [42] Learning effect and deteriorating jobs in the single machine scheduling problems
    Wang, Ji-Bo
    Huang, Xue
    Wang, Xiao-Yuan
    Yin, Na
    Wang, Li-Yan
    APPLIED MATHEMATICAL MODELLING, 2009, 33 (10) : 3848 - 3853
  • [43] Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan
    Jatinder N.D. Gupta
    Christos P. Koulamas
    George J. Kyparisis
    Chris N. Potts
    Vitaly A. Strusevich
    Annals of Operations Research, 2004, 129 : 171 - 185
  • [44] An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs
    Hadda, Hatem
    Dridi, Najoua
    Hajri-Gabouj, Sonia
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (01): : 87 - 99
  • [45] Single Machine Two-Agent Scheduling with Deteriorating Jobs
    Wang, Zhenyou
    Wei, Cai-Min
    Wu, Yu-Bin
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2016, 33 (05)
  • [46] Scheduling three-operation jobs in a two-machine flow shop to minimize makespan
    Gupta, JND
    Koulamas, CP
    Kyparisis, GJ
    Potts, CN
    Strusevich, VA
    ANNALS OF OPERATIONS RESEARCH, 2004, 129 (1-4) : 171 - 185
  • [47] Scheduling linear deteriorating jobs with rejection on a single machine
    Cheng, Yushao
    Sun, Shijie
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 194 (01) : 18 - 27
  • [48] Considerations of single-machine scheduling with deteriorating jobs
    Zhao, Chuan-Li
    Hsu, Chou-Jung
    Yang, Dar-Li
    APPLIED MATHEMATICAL MODELLING, 2011, 35 (10) : 5134 - 5142
  • [49] Scheduling deteriorating jobs to minimize the makespan on a single machine
    Wu, Chin-Chia
    Shiau, Yau-Ren
    Lee, Ling-Huei
    Lee, Wen-Chiung
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 44 (11-12) : 1230 - 1236
  • [50] Parallel-machine scheduling with deteriorating jobs and rejection
    Li, Shisheng
    Yuan, Jinjiang
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) : 3642 - 3650
12345