Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine open shop. Issue 4 (3rd April 2018) - Jiang, Fuhong; Zhang, Xingong; Bai, Danyu; Wu, Chin-Chia
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.