Subset-restricted interchange for dynamic min-max scheduling problems (Q2706175)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1578810
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Subset-restricted interchange for dynamic min-max scheduling problems |
scientific article; zbMATH DE number 1578810 |
Statements
19 March 2001
0 references
precedence order
0 references
branch and bound
0 references
Subset-restricted interchange for dynamic min-max scheduling problems (English)
0 references
This paper deals with scheduling two specific jobs within a sequence of \(n\) jobs, i.e. the so-called pair-wise job interchange problem. This problem is extended to the case that interchanging of the two given jobs is permitted only, if the intermediate jobs belong to a restricted subclass of jobs. The problem then is to determine the order of the two jobs which is optimal with respect to a cost function. In order to solve the problem efficiently a precedence order is derived and utilized by the subsequently applied branch and bound algorithm. By means of numerical examples it is shown that the algorithm with precedence order saves on an average about 58\% of the CPU time compared with an algorithm without precedence order necessary for solving the problem.
0 references
0.7639151215553284
0 references
0.7625594139099121
0 references
0.7504218816757202
0 references
