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 条
  • [1] An open shop scheduling problem with a non-bottleneck machine
    Strusevich, VA
    Hall, LA
    OPERATIONS RESEARCH LETTERS, 1997, 21 (01) : 11 - 18
  • [2] Two-machine Shop Scheduling with Two Agents and Linear Deteriorating Jobs
    Zhao, Xiaoli
    Wang, Gongshu
    2015 27TH CHINESE CONTROL AND DECISION CONFERENCE (CCDC), 2015, : 1154 - 1159
  • [3] A two-machine flowshop scheduling problem with deteriorating jobs and blocking
    Lee, Wen-Chiung
    Shiau, Yau-Ren
    Chen, Shiuan-Kang
    Wu, Chin-Chia
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2010, 124 (01) : 188 - 197
  • [4] A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints
    Zhao, Chuanli
    Tang, Hengyong
    OPTIMIZATION LETTERS, 2011, 5 (01) : 183 - 190
  • [5] Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints
    Zhao, Chuanli
    Tang, Hengyong
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2012, 136 (01) : 131 - 136
  • [6] Two-machine flow shop total tardiness scheduling problem with deteriorating jobs
    Bank, M.
    Ghomi, S. M. T. Fatemi
    Jolai, F.
    Behnamian, J.
    APPLIED MATHEMATICAL MODELLING, 2012, 36 (11) : 5418 - 5426
  • [7] Parallel machine scheduling problems with proportionally deteriorating jobs
    Cheng, Mingbao
    Wang, Guoqing
    He, Longmin
    INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2009, 40 (01) : 53 - 57
  • [8] Two-agent scheduling in a two-machine open shop
    Liu, Peihai
    Gu, Manzhan
    Lu, Xiwen
    ANNALS OF OPERATIONS RESEARCH, 2024, 333 (01) : 275 - 301
  • [9] A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints
    Chuanli Zhao
    Hengyong Tang
    Optimization Letters, 2011, 5 : 183 - 190
  • [10] Two-agent scheduling in a two-machine open shop
    Peihai Liu
    Manzhan Gu
    Xiwen Lu
    Annals of Operations Research, 2024, 333 : 275 - 301
12345