An exact method for Pm / sds,ri /∑ni=1 Ci problem

Rabia Nessah (1) , Chengbin Chu (1) , Farouk Yalaoui (1)

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

This paper addresses an identical parallel machine scheduling problem, with sequence-dependent setup times and release dates to minimize total completion time. This problem is known to be strongly NP-hard. We prove a sufficient and necessary condition for local optimality which can also be considered as a priority rule. We then define a dominant subset based on this condition. We present efficient heuristic algorithms using this condition to build a schedule belonging to this subset. We also prove dominance theorem, and develop a lower bound that can be computed in polynomial time. We construct a branch-and-bound algorithm in which the heuristic, the lower bound and the dominance properties are incorporated. Computational experiments suggest that the algorithm can handle test problems with 40 jobs and 2 machines.

Mots clés: Identical parallel machine; Scheduling; Setup time; Release dates; Lower bound; Dominance properties; Heuristic

Domaines: Recherche opérationnelle [math.OC]

Rabia Nessah, Chengbin Chu, Farouk Yalaoui. An exact method for Pm / sds,ri /∑ni=1 Ci problem. Computers and Operations Research, 2007, 34 (9), pp.2840-2848. ⟨10.1016/j.cor.2005.10.017⟩. ⟨hal-02490590⟩