Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective |
| |
Authors: | Stéphane Dauzère-Pérès Lars Mönch |
| |
Affiliation: | 1. Department of Manufacturing Sciences and Logistics, Centre Microélectronique de Provence – Site Georges Charpak, Ecole des Mines de Saint-Etienne, F-13541 Gardanne, France;2. Department of Mathematics and Computer Science, University of Hagen, D-58097 Hagen, Germany |
| |
Abstract: | In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time. |
| |
Keywords: | Scheduling Batching Mixed integer linear programming Genetic algorithms |
本文献已被 ScienceDirect 等数据库收录! |