Citation
Lawler's minmax cost algorithm: optimality conditions and uncertainty. Journal of Scheduling, 19 (4): 401-408, 2016.
Selected
Abstract
The well-known 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 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.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10951-014-0413-x You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@ARTICLE{2016-401-408-SI, author = {Brauner, Nadia and Finke, Gerd and Shafransky, Yakov and Sledneu, Dzmitry},
title = {{Lawler's minmax cost algorithm: optimality conditions and uncertainty}},
journal = {Journal of Scheduling},
year = {2016},
volume = {{19}},
pages = {401--408},
number = {4},
note = {Selected},
abstract = {{The well-known 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 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.}},
doi = {{10.1007/s10951-014-0413-x}},
eissn = {{1099-1425}},
issn = {{1094-6136}},
owner = {Graham},
timestamp = {2017.01.18},
unique-id = {{ISI:000379627200004}} }