Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Författare

  • Nadia Brauner
  • Gerd Finke
  • Yakov Shafransky
  • Dzmitry Sledneu

Summary, in English

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.

Publiceringsår

2015-01-04

Språk

Engelska

Publikation/Tidskrift/Serie

Journal of Scheduling

Dokumenttyp

Artikel i tidskrift

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • Lawler’s minmax cost algorithm
  • Uncertainty
  • Maximum regret

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1094-6136