Lawler’s minmax cost algorithm: optimality conditions and uncertainty
(2015) In Journal of Scheduling Abstract
 The wellknown 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 wellknown 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:
http://lup.lub.lu.se/record/7866177
 author
 Brauner, Nadia; Finke, Gerd; Shafransky, Yakov and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 20150104
 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
 10946136
 DOI
 10.1007/s109510140413x
 language
 English
 LU publication?
 yes
 id
 28115b19e2964fc6968a96cac48cb701 (old id 7866177)
 date added to LUP
 20150917 14:51:31
 date last changed
 20170101 03:50:11
@article{28115b19e2964fc6968a96cac48cb701, abstract = {The wellknown 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 = {10946136}, 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/s109510140413x}, year = {2015}, }