Abstract
| Original language | English |
|---|---|
| Place of Publication | Eindhoven |
| Publisher | Technische Universiteit Eindhoven |
| Number of pages | 40 |
| Publication status | Published - 1995 |
Publication series
| Name | Memorandum COSOR |
|---|---|
| Volume | 9537 |
| ISSN (Print) | 0926-4493 |
Fingerprint
Cite this
}
Nonstrict vector simulation in multi-operation scheduling. / Sevastianov, S.V.
Eindhoven : Technische Universiteit Eindhoven, 1995. 40 p. (Memorandum COSOR; Vol. 9537).Research output: Book/Report › Report › Academic
TY - BOOK
T1 - Nonstrict vector simulation in multi-operation scheduling
AU - Sevastianov, S.V.
PY - 1995
Y1 - 1995
N2 - We consider several multi??operation scheduling problems with m machines and n jobs??, including fl??ow shop??, open shop,?? assembly line,?? and a few special cases of job shop with the makespan criterion. It is demonstrated that the problems in question can be effi??ciently solved by approximation algorithms with fairly good performance guaranteed in worst case. The algorithms constructed are based on a geometric technique called "??nonstrict vector summation".?? It consists of assigning an (m-1)-????dimensional vector to each job and then ??finding an order in which the resulting vectors should be summed so that all partial sums lied within half??-spaces of the best possible family (with respect to a certain objective function).?? The partial sums are allowed sometimes go out of this or that half-??space of the family,?? which explains the term "??nonstrict??" in the title of the paper. For the open shop problem this technique guarantees its polynomial??-time solution,?? provided that the maximum machine load (lmax)?? is large enough. In the case of three machines and lmax as large as at least 7 times the maxi??mum processing time of an operation,?? we can ??find the optimal schedule in O(n logn??) time. Keywords:?? open??-shop,?? fl??ow shop,?? job shop,?? scheduling,?? polynomial-??time approximation algorithms??, sequencing of vectors.
AB - We consider several multi??operation scheduling problems with m machines and n jobs??, including fl??ow shop??, open shop,?? assembly line,?? and a few special cases of job shop with the makespan criterion. It is demonstrated that the problems in question can be effi??ciently solved by approximation algorithms with fairly good performance guaranteed in worst case. The algorithms constructed are based on a geometric technique called "??nonstrict vector summation".?? It consists of assigning an (m-1)-????dimensional vector to each job and then ??finding an order in which the resulting vectors should be summed so that all partial sums lied within half??-spaces of the best possible family (with respect to a certain objective function).?? The partial sums are allowed sometimes go out of this or that half-??space of the family,?? which explains the term "??nonstrict??" in the title of the paper. For the open shop problem this technique guarantees its polynomial??-time solution,?? provided that the maximum machine load (lmax)?? is large enough. In the case of three machines and lmax as large as at least 7 times the maxi??mum processing time of an operation,?? we can ??find the optimal schedule in O(n logn??) time. Keywords:?? open??-shop,?? fl??ow shop,?? job shop,?? scheduling,?? polynomial-??time approximation algorithms??, sequencing of vectors.
M3 - Report
T3 - Memorandum COSOR
BT - Nonstrict vector simulation in multi-operation scheduling
PB - Technische Universiteit Eindhoven
CY - Eindhoven
ER -