Scheduling identical jobs on uniform machines with a conflict graph

作     者：Mallek, Amin Bendraouche, Mohamed Boudhar, Mourad 

作者机构：USTHB Univ RECITS Lab Fac Math BP 32 El Alia Algiers Algeria Saad Dahleb Univ Fac Sci Route Soumaa BlidaBP Blida 270 Blida Algeria 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2019年第111卷

页      面：357-366页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Scheduling Identical jobs Incompatible jobs Uniform machines Conflict graph Mixed-integer linear programming 

摘      要：This paper addresses the problem of scheduling n identical jobs on a set of m parallel uniform machines. The jobs are subjected to conflicting constraints modelled by an undirected graph G, in which adjacent jobs are not allowed to be processed on the same machine. Minimising the maximum completion time in the schedule (makespan C-max) is known to be NP-hard. We prove that when G is restricted to complete bipartite graphs the problem remains NP-hard for arbitrary number of machines, however, if m is fixed an optimal solution can be obtained in polynomial time. To solve the general case of the problem, we propose mixed-integer linear programming (MILP) formulations alongside with lower bounds and heuristic approaches. Furthermore, computational experiments are carried out to measure the performance of the proposed methods. (C) 2019 Published by Elsevier Ltd.