Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

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.
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00773587
Contributor : Stéphane Dauzère-Pérès <>
Submitted on : Monday, January 14, 2013 - 1:02:35 PM
Last modification on : Monday, February 25, 2019 - 10:26:08 AM

Identifiers

Collections

Citation

Stéphane Dauzère-Pérès, Lars Moench. Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective. Computers and Operations Research, Elsevier, 2013, 40 (5), pp.1224-1233. ⟨10.1016/j.cor.2012.12.012⟩. ⟨emse-00773587⟩

Share

Metrics

Record views

152