A sequence algorithm for minimising makespan in multi-part and multi-machine flowshop cases

Abstract

Minimising makespan aims to achieve high utilisation of equipment and resources by getting all jobs out quickly. This is an important scheduling criterion, especially for automated systems, because of the high investment cost. The problem, however, becomes complex when many parts and machines are involved. This is because different parts may require different numbers of operations, and there are many possible schedules. For small problems, a mathematical programming model for minimising makespan is formulated. For large problems, a sequencing algorithm based on decomposition and pairwise comparison is proposed. The idea of "total overlapping time" in the sequencing algorithm is introduced to determine the solution of each sub-schedule. It maximises the number of jobs working at different machines at the same time, while satisfying the parts' operation precedence and machine constraints. The differences between this method and the traditional graphical method are discussed. The sequencing algorithm significantly reduces the number of schedules for consideration and hence, the computational power required. © MCB University Press.