Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem

References

• Alvim A. C. F., Ribeiro C. C., Ribeiro C. C., Martins S. L. A hybrid bin-packing heuristic to multiprocessor scheduling. Lecture Notes in Computer Science (2004) 3059(Springer-Verlag, Berlin) 1–13Crossref, Google Scholar
• Blum M., Floyd R. W., Pratt V., Rivest R. L., Tarjan R. E. Time bounds for selection. J. Comput. System Sci. (1973) 7:448–461Crossref, Google Scholar
• Brucker P.Scheduling Algorithms (2001) (Springer-Verlag, New York) Crossref, Google Scholar
• Chen B., Leung J. Y. T. Parallel scheduling for early completion. Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004) (CRC Press, Boca Raton, FL) 175–184Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. (1978) 7:1–17Crossref, Google Scholar
• Dell'Amico M., Martello S. Optimal scheduling of tasks on identical parallel processors. ORSA J. Comput. (1995) 7:191–200Link, Google Scholar
• Dell'Amico M., Martello S. A note on exact algorithms for the identical parallel machine scheduling problem. Eur. J. Oper. Res. (2005) 160:576–578Crossref, Google Scholar
• Dell'Amico M., Iori M., Martello S. Heuristic algorithms and scatter search for the cardinality constrained P‖Cmax problem. J. Heuristics (2004) 10:169–204Crossref, Google Scholar
• Fekete S. P., Schepers J. New classes of fast lower bounds for bin packing problems. Math. Programming (2001) 91:11–31Crossref, Google Scholar
• Fischetti M., Martello S., Simeone B., Toth P., Gallo G., Maffioli F., Pallottino S. A hybrid algorithm for finding the k-th smallest of n elements in O(n) time. FORTRAN Codes for Network Optimization, Vol. 13. Annals of Operations Research (1988) (J. C. Baltzer AG, Basel, Switzerland) 401–419Google Scholar
• França P. M., Gendreau M., Laporte G., Müller F. M. A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Comput. Oper. Res. (1994) 21:205–210Crossref, Google Scholar
• Frangioni A., Necciari E., Scutellà M. G. A multi-exchange neighborhood for minimum makespan machine scheduling problems. (2000) . Technical Report TR-00-17, Dipartimento di Informatica, Università di Pisa, Pisa, ItalyGoogle Scholar
• Frangioni A., Necciari E., Scutellà M. G. A multi-exchange neighborhood for minimum makespan machine scheduling problems. J. Combin. Optim. (2004) 8:195–220Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman, San Francisco) Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9:849–859Link, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem—Part II. Oper. Res. (1963) 11:863–888Link, Google Scholar
• Glover F., Laguna M., Martí R., Onwubolu G. C., Babu B. V. Scatter search and path relinking: Foundations and advanced designs. New Optimization Techniques in Engineering (2004) (Springer-Verlag, Heidelberg, Germany) 87–99Crossref, Google Scholar
• Graham R. L. Bounds for certain multiprocessing anomalies. Bell System Tech. J. (1966) 45:1563–1581Crossref, Google Scholar
• Graham R. L. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. (1969) 17:416–429Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Hochbaum D. S., Shmoys D. B. Using dual approximation algorithms for scheduling problems: Practical and theoretical results. J. ACM (1987) 34:144–162Crossref, Google Scholar
• Hoogeveen A., Lenstra J. K., van de Velde S. L., Dell'Amico M., Maffioli F., Martello S. Sequencing and scheduling. Annotated Bibliographies in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, UK) 181–197Google Scholar
• Johnson D. S., Demers A., Ullman J. D., Garey M. R., Graham R. L. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. (1974) 3:299–325Crossref, Google Scholar
• Leung J. Y. T.Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004) (CRC Press, Boca Raton, FL) Crossref, Google Scholar
• Martello S., Toth P. Worst-case analysis of greedy algorithms for the subset-sum problem. Math. Programming (1984) 28:198–205Crossref, Google Scholar
• Martello S., Toth P. Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. (1990a) 28:59–70Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990b) (John Wiley & Sons, Chichester, UK) . http://www.or.deis.unibo.it/knapsack.htmlGoogle Scholar
• Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Sci. (1999) 45:414–424Link, Google Scholar
• Martí R., Laguna M., Glover F. Principles of scatter search. Eur. J. Oper. Res. (2006) 169:359–372Crossref, Google Scholar
• Mokotoff E. Parallel machine scheduling problems: A survey. Asia-Pacific J. Oper. Res. (2001) 18:193–242Google Scholar
• Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem. Eur. J. Oper. Res. (2004) 152:758–769Crossref, Google Scholar
• Mokotoff E., Jimeno J. J., Gutiérrez I. List scheduling algorithms to minimize the makespan on identical parallel machines. TOP (2001) 9:243–269Crossref, Google Scholar