A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity

This paper studies an unrelated parallel machine scheduling problem with deteriorating maintenance activities, parallel-batching processing, and deteriorating jobs. Practically, deteriorating maintenance activities mean that durations of maintenance activities will increase with their starting time. The objective is to make the joint decisions on jobs assignments, the maintenance arrangements, jobs batching, and batches sequencing on each machine to minimize the makespan. Firstly, we formulate a mixed integer programming model for the problem. Then, we analyze a special case where all jobs have been assigned to machines and provide polynomial time optimal algorithms. Furthermore, since the studied problem is NP-hard, we develop a hybrid ABC-TS algorithm combining artificial bee colony (ABC) and Tabu Search (TS) to solve the problem in a reasonable time. Extensive computational experiments are conducted and the results validate the effectiveness and robustness of our proposed algorithms.