Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine open shop. Issue 4 (3rd April 2018)

• Record Type: Journal Article
• Authors: Jiang, Fuhong; Zhang, Xingong; Bai, Danyu; Wu, Chin-Chia
• Is Part Of: Engineering optimization. Volume 50:Issue 4(2018)
• Page Start: 684
• Page End: 697
• Publication Date: 2018-04-03
• Subjects: Two competitive agents -- open-shop scheduling -- makespan -- approximation algorithm; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2017.1332762
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: 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.