Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10346193 | Computers & Operations Research | 2013 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Stéphane Dauzère-Pérès, Lars Mönch,