Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine openshop

被引：8
作者：
Jiang, Fuhong [1 ,2 ]
Zhang, Xingong [1 ,2 ]
Bai, Danyu [3 ]
Wu, Chin-Chia [4 ]
机构：
[1] Chongqing Normal Univ, Coll Math Sci, Chongqing, Peoples R China
[2] Minist Educ, Key Lab Optimizat & Control, Chongqing, Peoples R China
[3] Shengyang Univ Chem Technol, Sch Econ & Management, Shenyang, Peoples R China
[4] Feng Chia Univ, Dept Stat, Taichung, Taiwan
来源：
ENGINEERING OPTIMIZATION | 2018年 / 50卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Two competitive agents; open-shop scheduling; makespan; approximation algorithm; OPEN SHOP; SINGLE-MACHINE; AGENTS; TIME;
D O I：
10.1080/0305215X.2017.1332762
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
In this article, a competitive two-agent scheduling problem in a two-machine open shop is studied. The objective is to minimize the weighted sum of the makespans of two competitive agents. A complexity proof is presented for minimizing the weighted combination of the makespan of each agent if the weight belonging to agent B is arbitrary. Furthermore, two pseudo-polynomial-time algorithms using the largest alternate processing time (LAPT) rule are presented. Finally, two approximation algorithms are presented if the weight is equal to one. Additionally, another approximation algorithm is presented if the weight is larger than one.
引用
收藏
页码：684 / 697
页数：14
相关论文
共 25 条
  • [1] Scheduling problems with two competing agents
    Agnetis, A
    Mirchandani, PB
    Pacciarelli, D
    Pacifici, A
    [J]. OPERATIONS RESEARCH, 2004, 52 (02) : 229 - 242
  • [2] Agnetis A., 2014, MULTIAGENT SCHEDULIN
  • [3] Multi-agent single machine scheduling
    Agnetis, Alessandro
    Pacciarelli, Dario
    Pacifici, Andrea
    [J]. ANNALS OF OPERATIONS RESEARCH, 2007, 150 (01) : 3 - 15
  • [4] Single-machine earliness-tardiness scheduling with two competing agents and idle time
    Ahmadizar, Fardin
    Eteghadipour, Jafar
    [J]. ENGINEERING OPTIMIZATION, 2017, 49 (03) : 499 - 512
  • [5] A novel hybrid genetic algorithm for the open shop scheduling problem
    Ahmadizar, Fardin
    Farahani, Mehdi Hosseinabadi
    [J]. INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 62 (5-8) : 775 - 787
  • [6] Open shop scheduling problem to minimize total weighted completion time
    Bai, Danyu
    Zhang, Zhihai
    Zhang, Qiang
    Tang, Mengqian
    [J]. ENGINEERING OPTIMIZATION, 2017, 49 (01) : 98 - 112
  • [7] Flexible open shop scheduling problem to minimize makespan
    Bai, Danyu
    Zhang, Zhi-Hai
    Zhang, Qiang
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2016, 67 : 207 - 215
  • [8] A multiple-criterion model for machine scheduling
    Baker, KR
    Smith, JC
    [J]. JOURNAL OF SCHEDULING, 2003, 6 (01) : 7 - 16
  • [9] Chen B., 1993, ORSA Journal on Computing, V5, P321, DOI 10.1287/ijoc.5.3.321
  • [10] Chen B., 1998, Handbook of Combinatorial Optimization, P1493, DOI [DOI 10.1007/978-1-4613-0303-9_25, 10.1007/978-1-4613-0303-925, DOI 10.1007/978-1-4613-0303-925]
123