Abstract | ||
---|---|---|
We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish-start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open. |
Year | DOI | Venue |
---|---|---|
2019 | 10.3390/a12120250 | ALGORITHMS |
Keywords | Field | DocType |
job shop,flow shop,s-precedence constraints,exact algorithms,complexity | Mathematical optimization,Polynomial,Scheduling (computing),Job shop,Flow shop scheduling,Operations research,Mathematics | Journal |
Volume | Issue | Citations |
12 | 12 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alessandro Agnetis | 1 | 408 | 30.67 |
Fabrizio Rossi | 2 | 140 | 16.33 |
Stefano Smriglio | 3 | 153 | 14.81 |