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 条
  • [31] Two-machine flow-shop scheduling with rejection
    Shabtay, Dvir
    Gasper, Nufar
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (05) : 1087 - 1096
  • [32] Single-machine scheduling with deteriorating jobs
    Kuo, Wen-Hung
    Yang, Dar-Li
    INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2012, 43 (01) : 132 - 139
  • [33] Scheduling Two-machine Flow Shop with a Batch Processing Machine
    Koh, Shiegheun
    Kim, Youngjin
    Lee, Woonseek
    CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 46 - 51
  • [34] Two-agent single-machine scheduling with deteriorating jobs
    Yin, Yunqiang
    Cheng, T. C. E.
    Wan, Long
    Wu, Chin-Chia
    Liu, Jun
    COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 81 : 177 - 185
  • [35] Two-agent group scheduling with deteriorating jobs on a single machine
    Liu, Peng
    Tang, Lixin
    Zhou, Xiaoye
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2010, 47 (5-8) : 657 - 664
  • [36] Scheduling with Deteriorating Jobs and Non-Simultaneous Machine Available Times
    Wang, Xuyin
    Hu, Xiangpei
    Liu, Weiguo
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2015, 32 (06)
  • [37] Two-machine open shop problem with agreement graph
    Tellache, Nour El Houda
    Boudhar, Mourad
    Yalaoui, Farouk
    THEORETICAL COMPUTER SCIENCE, 2019, 796 : 154 - 168
  • [38] Unrelated parallel-machine scheduling with deteriorating jobs and rejection
    Hsu, Chou-Jung
    Chang, Chia-Wen
    INFORMATION TECHNOLOGY APPLICATIONS IN INDUSTRY, PTS 1-4, 2013, 263-266 : 655 - 659
  • [39] Single-machine scheduling with learning effect and deteriorating jobs
    Wang, Ji-Bo
    COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 57 (04) : 1452 - 1456
  • [40] An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs
    Hatem Hadda
    Najoua Dridi
    Sonia Hajri-Gabouj
    4OR, 2010, 8 : 87 - 99
12345