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 条
  • [21] Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time
    Cheng, Mingbao
    Tadikamalla, Pandu R.
    Shang, Jennifer
    Zhang, Bixi
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2015, 66 (05) : 709 - 719
  • [22] Scheduling Piecewise Linear Deteriorating Jobs to Minimize Makespan in a Two-Machine Flowshop
    Jafari-Nodoushan A.
    Zare H.K.
    Lotfi M.M.
    Tavakkoli-Moghaddam R.
    Operations Research Forum, 2 (4)
  • [23] A two-machine flow-shop scheduling with a deteriorating maintenance activity on the second machine
    Gara-Ali, Ahmed
    Espinouse, Marie-Laure
    2015 INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND SYSTEMS MANAGEMENT (IESM), 2015, : 481 - 488
  • [24] Minimizing total completion time in a two-machine flow shop with deteriorating jobs
    Wang, Ji-Bo
    Ng, C. T. Daniel
    Cheng, T. C. E.
    Liu, Li-Li
    APPLIED MATHEMATICS AND COMPUTATION, 2006, 180 (01) : 185 - 193
  • [25] Two-machine open-shop scheduling with rejection to minimize the makespan
    Liqi Zhang
    Lingfa Lu
    Jinjiang Yuan
    OR Spectrum, 2016, 38 : 519 - 529
  • [26] Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs
    Cheng, Mingbao
    Tadikamalla, Pandu R.
    Shang, Jennifer
    Zhang, Shaqing
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 234 (03) : 650 - 657
  • [27] Two-machine open-shop scheduling with rejection to minimize the makespan
    Zhang, Liqi
    Lu, Lingfa
    Yuan, Jinjiang
    OR SPECTRUM, 2016, 38 (02) : 519 - 529
  • [28] Two-machine flow shop and open shop scheduling problems with a single maintenance window
    Mosheiov, Gur
    Sarig, Assaf
    Strusevich, Vitaly A.
    Mosheiff, Jonathan
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 271 (02) : 388 - 400
  • [29] Two-machine flow shop scheduling with linear decreasing job deterioration
    Wang, Ji-Bo
    Liu, Li-Li
    COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (04) : 1487 - 1493
  • [30] Approximation algorithms for two-machine open shop scheduling with batch and delivery coordination
    Dong, Jianming
    Zhang, An
    Chen, Yong
    Yang, Qifan
    THEORETICAL COMPUTER SCIENCE, 2013, 491 : 94 - 102
12345