POLISH ACADEMY of SCIENCES
TECHNICAL SCIENCES
Analysis of Dynamic Systems and Mechanical Engineering
| BULLETIN
of the
POLISH ACADEMY of SCIENCES TECHNICAL SCIENCES |
|
|||
|---|---|---|---|---|
| Volume
55, Issue 1, March 2007
Analysis of Dynamic Systems and Mechanical Engineering |
||||
| Issue Index | Authors Index | Scope Index | Web Info | |
|
|
||||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files | mirror: http://fluid.ippt.gov.pl/~bulletin/ |
| pp 59 - 69 |
|---|
|
Dominance relations for two-machine flow shop problem with late work criterion |
|---|
| M. STERNA |
| The paper concerns the two-machine non-preemptive flow shop scheduling problem with a total late work criterion and a common due date (F2|dj = d|Y ). The late work performance measure estimates the quality of a solution with regard to the duration of late parts of activities performed in the system, not taking into account the quantity of this delay. In the paper, a few theorems are formulated and proven, describing features of an optimal solution for the problem mentioned, which is NP-hard. These theorems can be used in exact exponential algorithms (as dominance relations reducing the number of solutions enumerated explicitly), as well as in heuristic and metaheuristic methods (supporting the construction of sub-optimal schedules of a good quality). |
| Key words: |
|
scheduling, flow shop, late work criterion, dominance relation |
|
|
| Issue Index | Authors Index | Scope Index | Web Info |
|---|---|---|---|
|
|
|||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files |
| Copyright
® Bulletin of the Polish Academy of Sciences: Technical Sciences
30 March 2007, site prepared by KZ |
|---|