Branch-and-bound and PSO algorithms for no-wait job shop scheduling

This paper deals with the no-wait job shop scheduling problem resolution. The problem is to find a schedule to minimize the makespan (C-max), that is, the total completeness time of all jobs. The no-wait constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. For this, we have proposed two different resolution methods, the first is an exact method based on the branch-and-bound algorithm, in which we have defined a new technique of branching. The second is a particular swarm optimization (PSO) algorithm, extended from the discrete version of PSO. In the proposed algorithm, we have defined the particle and the velocity structures, and an efficient approach is developed to move a particle to the new position. Moreover, we have adapted the timetabling procedure to find a good solution while respecting the no-wait constraint. Using the PSO method, we have reached good results compared to those in the literature.