Minimising total completion time in no-wait flow shop scheduling with learning effects and group technology

In this paper, we consider the no-wait group flow shop scheduling problem in which the setup time is sequence-independent and the processing time of jobs have learning effects. Under the two-machines setting, the goal is to find an optimal schedule to minimise the total completion time. We show that this problem is NP-hard and then present two polynomial-solvable special cases. For the general problem, we first propose a simple heuristic algorithm and analyse its worst-case ratio, and then design a branch-and-bound algorithm and a mixed-integer linear programming model. Moreover, we also propose a group Nawaz-Enscore-Ham algorithm and a simulated annealing algorithm. Finally, the effectiveness and error of the proposed algorithms are compared through comparative experiment. The experimental results demonstrated that branch-and-bound algorithm can solve small sized problems well and group Nawaz-Enscore-Ham algorithm algorithm can solve medium and large sized problems well.