A single machine scheduling problem with availability constraints and sequence-dependent setup costs |
| |
Authors: | Francisco Ángel-Bello Ada Álvarez Joaquín Pacheco Iris Martínez |
| |
Institution: | 1. Department of Industrial and Systems Engineering, Tecnológico de Monterrey, Campus Monterrey, Nuevo León, Mexico;2. Graduated Program in Systems Engineering, Universidad Autónoma de Nuevo León, San Nicolás, Nuevo León, Mexico;3. Department of Applied Economics, Universidad de Burgos, Burgos, Spain |
| |
Abstract: | We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic. |
| |
Keywords: | Scheduling problem Availability constraints Setup costs Mixed integer model Valid inequality |
本文献已被 ScienceDirect 等数据库收录! |
|