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

Abstract

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.

Keywords:

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

Acknowledgements

We thank the referees and Editors for their comments and suggestions that have greatly improved the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported in part by National Science Foundation of China [grant number 71690232]; National Science Foundation [grant number CMMI-1536978].