Parallel machine scheduling through column generation: Minimax objective functions (extended abstract) (2024)

Van Den Akker, J. M., Hoogeveen, J. A., & Van Kempen, J. W. (2006). Parallel machine scheduling through column generation: Minimax objective functions (extended abstract). In Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings (pp. 648-659). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer. https://doi.org/10.1007/11841036_58

Van Den Akker, J. M. ; Hoogeveen, J. A. ; Van Kempen, J. W. / Parallel machine scheduling through column generation : Minimax objective functions (extended abstract). Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Springer, 2006. pp. 648-659 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3384d20e35e240eda97def206c0981df,

title = "Parallel machine scheduling through column generation: Minimax objective functions (extended abstract)",

abstract = "In this paper we consider one of the basic problems in scheduling and project management: scheduling on parallel identical machines. We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints. Our framework is based on column generation. Although column generation has been successfully applied to many parallel machine scheduling problems with objective functions of the minsum type, the number of applications for minimax objective functions is still small. We determine a lower bound on the objective function in the following way. We first turn the minimization problem into a decision problem by bounding the outcome value. We then ask ourselves 'Are m machines enough to feasibly accommodate all jobs?'. We formulate this as an integer linear programming problem and we determine a high quality lower bound by applying column generation to the LP-relaxation; if this lower bound is more than m, then we can conclude infeasibility. To speed up the process, we compute an intermediate lower bound based on the outcome of the pricing problem. As the pricing problem is intractable for many variants of the original scheduling problem, we mostly solve it approximately by applying local search, but once in every 50 iterations or when local search fails, we use a time-indexed integer linear programming formulation to solve the pricing problem. After having derived the lower bound on the objective function of the original scheduling problem, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this almost always succeeds. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.",

keywords = "Column generation, Intermediate lower bounds, Linear programming, Maximum lateness, Parallel machine scheduling, Precedence constraints, Release dates, Set covering formulation, Time-indexed formulation",

author = "{Van Den Akker}, {J. M.} and Hoogeveen, {J. A.} and {Van Kempen}, {J. W.}",

year = "2006",

doi = "10.1007/11841036_58",

language = "English",

isbn = "3540388753",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "648--659",

booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",

note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",

}

Van Den Akker, JM, Hoogeveen, JA & Van Kempen, JW 2006, Parallel machine scheduling through column generation: Minimax objective functions (extended abstract). in Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4168 LNCS, Springer, pp. 648-659, 14th Annual European Symposium on Algorithms, ESA 2006, Zurich, Switzerland, 11/09/06. https://doi.org/10.1007/11841036_58

Parallel machine scheduling through column generation: Minimax objective functions (extended abstract). / Van Den Akker, J. M.; Hoogeveen, J. A.; Van Kempen, J. W.
Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Springer, 2006. p. 648-659 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Parallel machine scheduling through column generation

T2 - 14th Annual European Symposium on Algorithms, ESA 2006

AU - Van Den Akker, J. M.

AU - Hoogeveen, J. A.

AU - Van Kempen, J. W.

PY - 2006

Y1 - 2006

N2 - In this paper we consider one of the basic problems in scheduling and project management: scheduling on parallel identical machines. We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints. Our framework is based on column generation. Although column generation has been successfully applied to many parallel machine scheduling problems with objective functions of the minsum type, the number of applications for minimax objective functions is still small. We determine a lower bound on the objective function in the following way. We first turn the minimization problem into a decision problem by bounding the outcome value. We then ask ourselves 'Are m machines enough to feasibly accommodate all jobs?'. We formulate this as an integer linear programming problem and we determine a high quality lower bound by applying column generation to the LP-relaxation; if this lower bound is more than m, then we can conclude infeasibility. To speed up the process, we compute an intermediate lower bound based on the outcome of the pricing problem. As the pricing problem is intractable for many variants of the original scheduling problem, we mostly solve it approximately by applying local search, but once in every 50 iterations or when local search fails, we use a time-indexed integer linear programming formulation to solve the pricing problem. After having derived the lower bound on the objective function of the original scheduling problem, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this almost always succeeds. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.

AB - In this paper we consider one of the basic problems in scheduling and project management: scheduling on parallel identical machines. We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints. Our framework is based on column generation. Although column generation has been successfully applied to many parallel machine scheduling problems with objective functions of the minsum type, the number of applications for minimax objective functions is still small. We determine a lower bound on the objective function in the following way. We first turn the minimization problem into a decision problem by bounding the outcome value. We then ask ourselves 'Are m machines enough to feasibly accommodate all jobs?'. We formulate this as an integer linear programming problem and we determine a high quality lower bound by applying column generation to the LP-relaxation; if this lower bound is more than m, then we can conclude infeasibility. To speed up the process, we compute an intermediate lower bound based on the outcome of the pricing problem. As the pricing problem is intractable for many variants of the original scheduling problem, we mostly solve it approximately by applying local search, but once in every 50 iterations or when local search fails, we use a time-indexed integer linear programming formulation to solve the pricing problem. After having derived the lower bound on the objective function of the original scheduling problem, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this almost always succeeds. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.

KW - Column generation

KW - Intermediate lower bounds

KW - Linear programming

KW - Maximum lateness

KW - Parallel machine scheduling

KW - Precedence constraints

KW - Release dates

KW - Set covering formulation

KW - Time-indexed formulation

UR - http://www.scopus.com/inward/record.url?scp=33750695647&partnerID=8YFLogxK

U2 - 10.1007/11841036_58

DO - 10.1007/11841036_58

M3 - Conference contribution

AN - SCOPUS:33750695647

SN - 3540388753

SN - 9783540388753

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 648

EP - 659

BT - Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings

PB - Springer

Y2 - 11 September 2006 through 13 September 2006

ER -

Van Den Akker JM, Hoogeveen JA, Van Kempen JW. Parallel machine scheduling through column generation: Minimax objective functions (extended abstract). In Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Springer. 2006. p. 648-659. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11841036_58