Minimising total weighted completion time on batch and unary machines with incompatible job families

作者：Huang, Zewen; Shi, Zhongshun^*; Shi, Leyuan

来源：International Journal of Production Research, 2019, 57(2): 567-581.

DOI：10.1080/00207543.2018.1470341

• batch machine
• incompatible job families
• total weighted completion time
• approximation algorithm
• constraint programming

This paper addresses the problem of scheduling on batch and unary machines with incompatible job families such that the total weighted completion time is minimised. A mixed-integer linear programming model is proposed to solve the problem to optimality for small instances. Tight lower bounds and a 4-approximation algorithm are developed. A constraint programming-based method is also proposed. Numerical results demonstrate that the proposed algorithms can obtain high quality solutions and have a competitive performance. Sensitivity analysis indicates that the performance of the proposed algorithms is also robust on different problem structures.

• 出版日期2019-1-17
• 单位北京大学