A branch & bound method for the general-shop problem with sequence dependent setup-times
Autor(en): | Brucker, P Thiele, O |
Stichwörter: | ALGORITHM; block approach; branch & bound method; disjunctive graph model; general-shop problem; immediate selection; job-shop; open-shop; Operations Research & Management Science; sequence dependent setup-times | Erscheinungsdatum: | 1996 | Herausgeber: | SPRINGER VERLAG | Journal: | OR SPEKTRUM | Volumen: | 18 | Ausgabe: | 3 | Startseite: | 145 | Seitenende: | 161 | Zusammenfassung: | A branch & bound algorithm is presented for a very general scheduling problem with n jobs and m machines. Each job consists of a set of operations. Each operation has to be processed on a dedicated machine. There may be arbitrary precedence relations between the operations. The set of all operations is partitioned into groups. If on a machine an operation belonging to group G(g) is processed immediately after an operation belonging to group G(f) there is a setup of s(fg) time units. We assume that s(fg)=0 if f=g and that the s(fg) satisfy the triangle inequality. Computational results for this general problem as well as for special cases like the job-shop problem and the open-shop problem are reported. |
ISSN: | 01716468 |
Zur Langanzeige