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

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.

KEYWORDS:

• Two competitive agents
• open-shop scheduling
• makespan
• approximation algorithm

Disclosure statement

No potential conflict of interest was reported by the authors.