Ordinal algorithms for parallel machine scheduling
| Autor: | Jeffrey B. Sidney, André van Vliet, Wei-Ping Liu |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Mathematical optimization
Machine scheduling 021103 operations research Scheduling heuristics Applied Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Upper and lower bounds Industrial and Manufacturing Engineering Scheduling (computing) Arbitrarily large Performance ratio 010201 computation theory & mathematics Minification Completion time Algorithm Software Mathematics |
| Zdroj: | Operations Research Letters. 18:223-232 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/0167-6377(95)00058-5 |
| Popis: | The minimization of maximum completion time for scheduling n jobs on m identical parallel machines is an NP-hard problem for which many excellent heuristic algorithms have been developed. In this paper, the problem is investigated under the assumption that only limited information about the jobs is available. Specifically, processing times are not known for the jobs; rather, the ordering of the jobs by processing time is known. For the cases of two and three parallel machines, algorithms which cannot be improved upon with respect to worst case performance ratio are developed. For the case of four parallel machines, an algorithm which is near optimal with respect to worst case performance ratio is developed. For arbitrary m, an algorithm which produces solutions whose value is at most five-thirds times the optimal value is presented. Finally, it is shown that as the number of machines gets arbitrarily large, the best possible ordinal algorithm has worst case performance ratio of at least 32. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect