An improved branch and bound algorithm for solving the identical parallel machnmes scheduling problem with family setup times

Belgacem Bettayeb (1) , Imed Kacem (2) , Kondo Hloindo Adjallah (1)

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

This article investigates identical parallel machines scheduling with family setups. The objective function is the sum of the weighted completion times. We propose an efficient constructive heuristic and three complementary lower bounding methods that we incorporate in a branch-and-bound algorithm. The results obtained by the above algorithm are satisfactory and encouraging

Keywords: Scheduling algorithm; Job shop scheduling; Parallel machines; Noise measurement; Systems engineering and theory; Processor scheduling; Job production systems; Frequency; Costs; Lagrangian functions; Scheduling; Branch and bound; Identical parallel machines; Family setup times

Domains: Computer Science [cs]; Operations Research [cs.RO]

Belgacem Bettayeb, Imed Kacem, Kondo Hloindo Adjallah. An improved branch and bound algorithm for solving the identical parallel machnmes scheduling problem with family setup times. Multiconference on "Computational Engineering in Systems Applications, Oct 2006, Beijing, China. pp.1040-1046, ⟨10.1109/CESA.2006.4281800⟩. ⟨hal-02490601⟩