A Column Generation Method for the Parallel-Machine Scheduling Problem with availability constraint

Racem Mellouli (1) , Cherif Sadfi (1) , Chengbin Chu (1) , Imed Kacem (1, 2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes

In this paper, we study the problem of scheduling jobs on identical parallel machines with the objective of minimizing the total completion times of jobs where each machine is subject to one unavailability time interval. We provide a column generation based method to obtain a lower bound for the problem. Computational experiments show the interest and the versatility of the proposed method

Mots clés: Job shop scheduling; Parallel machines; Processor scheduling; Dynamic programming; Availability; Systems engineering and theory; Postal services; Integer linear programming; Electric breakdown; Preventive maintenance

Domaines: Recherche opérationnelle [math.OC]

Racem Mellouli, Cherif Sadfi, Chengbin Chu, Imed Kacem. A Column Generation Method for the Parallel-Machine Scheduling Problem with availability constraint. Multiconference on "Computational Engineering in Systems Applications, Oct 2006, Beijing, China. pp.1027-1033, ⟨10.1109/CESA.2006.4281798⟩. ⟨hal-02476030⟩