A three-agent scheduling problem for minimizing the flow time on two machines

¹ Department of Statistics, Feng Chia University, 40724 Taichung, Taiwan, R.O.C.
² Department of Computer Science and Information Management, Hungkuang University, 43302 Taichung, Taiwan, R.O.C.

^* Corresponding author: jywang@sunrise.hk.edu.tw

Received: 30 December 2018
Accepted: 6 September 2019

Abstract

This study introduces a two-machine three-agent scheduling problem. We aim to minimize the total tardiness of jobs from agent 1 subject to that the maximum completion time of jobs from agent 2 cannot exceed a given limit and that two maintenance activities from agent 3 must be conducted within two maintenance windows. Due to the NP-hardness of this problem, a genetic algorithm (named GA⁺) is proposed to obtain approximate solutions. On the other hand, a branch-and-bound algorithm (named B&B) is developed to generate the optimal solutions. When the problem size is small, we use B&B to verify the solution quality of GA⁺. When the number of jobs is large, a relative deviation is proposed to show the gap between GA⁺ and another ordinary genetic algorithm. Experimental results show that the proposed genetic algorithm can generate approximate solutions by consuming reasonable execution time.