Abstract | ||
---|---|---|
In a multiprocessor or distributed system, jobs may need to be executed on more than one processor. When all the jobs execute on different processors in turn in the same order, the problem of end-to-end scheduling on the processors is known as the flow-shop problem. The paper describes two optimal polynomial-time algorithms for scheduling jobs in flow shops to meet deadlines, for two special cases where the scheduling problem is tractable. For the general case, where an optimal polynomial-time algorithm is unlikely to be found, a heuristic algorithm is presented. |
Year | DOI | Venue |
---|---|---|
1990 | 10.1109/SPDP.1990.143508 | Dallas, TX |
Keywords | Field | DocType |
distributed system,real time systems,control systems,parallel algorithms,heuristic algorithm,scheduling,pipelines,scheduling algorithm,scheduling problem,job shop scheduling,polynomials,multiprocessor,throughput | Multiprocessor scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Parallel computing,Flow shop scheduling,Algorithm,Gang scheduling,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-2087-0 | 12 | 5.92 |
References | Authors | |
6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Riccardo Bettati | 1 | 744 | 72.39 |
Jane W.-S. Liu | 2 | 1399 | 337.97 |