Premium
Sensitivity analysis in the single‐machine scheduling problem with max–min criterion
Author(s) -
Chanas Stefan,
Kasperski Adam
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2005.00505.x
Subject(s) - mathematical optimization , single machine scheduling , scheduling (production processes) , computer science , job shop scheduling , sensitivity (control systems) , set (abstract data type) , sequence (biology) , mathematics , schedule , electronic engineering , biology , engineering , genetics , programming language , operating system
In this paper, the single‐machine scheduling problem 1∣ prec ∣ f max is considered. It is one of the most general scheduling problems for which an efficient, polynomial algorithm has been developed. It is always possible to calculate quickly one optimal solution (a sequence of jobs) in that problem. However, the set of all optimal solutions may contain a lot of other sequences, so it is important to give a full characterization of that set. This paper consists of two parts. In the first part, some sufficient and necessary conditions of optimality of a given solution to the problem 1∣ prec ∣ f max are proved. In the second part, an application of these conditions to the sensitivity analysis is presented.