Advanced

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Brauner, Nadia; Finke, Gerd; Shafransky, Yakov and Sledneu, Dzmitry LU (2015) In Journal of Scheduling
Abstract
The well-known O(n^2) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of... (More)
The well-known O(n^2) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an O(n^2) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Lawler’s minmax cost algorithm, Uncertainty, Maximum regret
in
Journal of Scheduling
publisher
Springer
external identifiers
  • scopus:84920517412
ISSN
1094-6136
DOI
10.1007/s10951-014-0413-x
language
English
LU publication?
yes
id
28115b19-e296-4fc6-968a-96cac48cb701 (old id 7866177)
date added to LUP
2015-09-17 14:51:31
date last changed
2017-01-01 03:50:11
@article{28115b19-e296-4fc6-968a-96cac48cb701,
  abstract     = {The well-known O(n^2) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an O(n^2) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.},
  author       = {Brauner, Nadia and Finke, Gerd and Shafransky, Yakov and Sledneu, Dzmitry},
  issn         = {1094-6136},
  keyword      = {Lawler’s minmax cost algorithm,Uncertainty,Maximum regret},
  language     = {eng},
  month        = {01},
  publisher    = {Springer},
  series       = {Journal of Scheduling},
  title        = {Lawler’s minmax cost algorithm: optimality conditions and uncertainty},
  url          = {http://dx.doi.org/10.1007/s10951-014-0413-x},
  year         = {2015},
}