A Branch-and-Bound to solve the scheduling problem Pm/r_j/ΣT_j

Farouk Yalaoui (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

This paper presents the first study for the total tardiness minimization on parallel machine scheduling problem with different release dates of jobs. In this problem, a set of jobs has to be scheduled, without any preemption or splitting, on identical parallel machine. Each job has a due date and a release date. A polynomial lower bound is proposed using a relaxation procedure. A set of dominance properties are also established. A branch and bound algorithm is developed by taking into account the theoretical properties, lower and also upper bounds. This exact method has been tested on a large number of randomly generated problems. The obtained results are promising.

Keywords: Parallel machines; Job shop scheduling; Polynomials; Upper bound; Testing; Random number generation; Simulated annealing; Production systems; Time measurement; Single machine scheduling; Scheduling; Identical parallel machines; Total tardiness; Release dates; Dominance properties; Lower bound; Branch and bound

Domains: Operations Research [cs.RO]

Farouk Yalaoui. A Branch-and-Bound to solve the scheduling problem Pm/r_j/ΣT_j. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.1199-1204, ⟨10.1109/ICSSSM.2006.320679⟩. ⟨hal-02474703⟩