A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times |
| |
Authors: | Manuel J Pereira Lopes JM Valério de Carvalho |
| |
Institution: | 1. Dept. de Engenharia Mecânica, Instituto Superior de Engenharia do Porto, Portugal;2. Dept. de Produção e Sistemas, Universidade do Minho, Portugal |
| |
Abstract: | We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time. |
| |
Keywords: | Parallel machines scheduling Setup times Column generation Branch-and-price |
本文献已被 ScienceDirect 等数据库收录! |