A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan |
| |
| Affiliation: | 1. Instituto de Computação, Universidade Federal Fluminense, Rua Passo da Pátria 156, São Domingos, 24210-240 Niterói, RJ, Brazil;2. Departamento de Sistemas de Computação, Centro de Informática, Universidade Federal da Paraíba, Rua dos Escoteiros, Mangabeira, 58058-600 João Pessoa, PB, Brazil;3. School of Management, University of Bath, Bath BA2 7AY, UK;4. Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montreal H3T 2A7, Canada |
| |
| Abstract: | This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost. |
| |
| Keywords: | Single machine scheduling Release dates Sequence-dependent setup times Beam search Makespan |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
