Job shop scheduling with a combination of four buffering constraints

Abstract

In this paper, a new scheduling problem is investigated in order to optimise a more generalised Job Shop Scheduling system with a Combination of four Buffering constraints (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) called CBJSS. In practice, the CBJSS is significant in modelling and analysing many real-world scheduling systems in chemical, food, manufacturing, railway, health care and aviation industries. Critical problem properties are thoroughly analysed in terms of the Gantt charts. Based on these properties, an applicable mixed integer programming model is formulated and an efficient heuristic algorithm is developed. Computational experiments show that the proposed heuristic algorithm is satisfactory for solving the CBJSS in real time.

Keywords:

• job shop scheduling
• buffer management
• blocking
• no-wait
• mixed integer programming
• constructive algorithm
• best-insertion-heuristic algorithm

Acknowledgement

The authors would like to acknowledge the partial support from the Cooperative Research Centre for Optimising Resource Extraction established by the Australian Government’s Cooperative Research Centres Programme as well as the National Natural Science Foundation of China under grant numbers. 71531003, 71571032 and 71572156.