Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines

References

• Bruno J. L., Coffman E. G., Sethi R. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM (1974) 17:382–387Crossref, Google Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics (1990) 26:255–270Crossref, Google Scholar
• Glass C. A., Potts C. N., Shade P. Unrelated parallel machine scheduling using local search. Mathematical and Computer Modelling (1994) 20:41–52Crossref, 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. Annals of Discrete Mathematics (1979) 5:287–326Crossref, Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: off-line and on-line algorithms. Mathematics of Operations Research (1997) 22:513–544Link, Google Scholar
• Hariri A. M. A., Potts C. N. Heuristics for scheduling unrelated parallel machines. Computers and Operations Research (1991) 18:323–331Crossref, Google Scholar
• Hoogeveen J. A., Schuurman P., Woeginger G. J. Nonapproximability results for scheduling problems with minsum criteria. Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO'98) (1998) (Springer, Berlin, Germany) 353–366LNCS 1412Crossref, Google Scholar
• Horn W. A. Minimizing average flow time with parallel machines. Operations Research (1973) 21:846–847Link, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The traveling salesman problem: a case study. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, U.K) Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics (1977) 1:343–362Crossref, Google Scholar
• Nowicki E., Smutnicki C. A fast taboo search algorithm for the job shop problem. Management Science (1996) 42:797–913Link, Google Scholar
• Phillips C., Stein C., Wein J. Task scheduling in networks. SIAM Journal on Discrete Mathematics (1997) 10:573–598Crossref, Google Scholar
• Savelsbergh M. W. P., Uma R. N., Wein J. An experimental study of linear programming-based scheduling heuristics. Proceedings of 8th ACM-SIAM Symposium on Discrete Algorithms (1998) (SIAM, Philadelphia, PA) 453–461Google Scholar
• Schulz A. S., Skutella M., Burkard R., Woeginger G. Scheduling-LPs bear probabilities: randomized approximations for min-sum criteria. Algorithms—ESA'97 (1997a) (Springer, Berlin, Germany) 416–429LNCS 1284Crossref, Google Scholar
• Schulz A. S., Skutella M., Rolim J. Random-based scheduling: new approximations and LP lower bounds. Randomization and Approximation Techniques in Computer Science (1997b) (Springer, Berlin, Germany) 119–133LNCS 1296Crossref, Google Scholar
• Shmoys D. B., Tardos E. An approximation algorithm for the generalized assignment problem. Mathematical Programming62:461–474Crossref, Google Scholar
• Skutella M.Approximation and Randomization in Scheduling (1998) . Ph.D. thesis, Fachbereich Mathematik, Technische Universität Berlin, Berlin, GermanyGoogle Scholar
• Skutella M. Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM (2001) 48:206–242Crossref, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Research Logistics Quarterly (1956) 3:59–66Crossref, Google Scholar
• Sturm J. F. Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software (1999) 11-12:625–653Crossref, Google Scholar
• Uma R. N., Wein J. On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems. IPCO: 6th Integer Programming and Combinatorial Optimization Conference (1998) (Springer, Berlin, Germany) . LNCS 1412Crossref, Google Scholar
• Van den Akker J. M., Hurkens C. A. J., Savelsbergh M. W. P. Time-indexed formulations for machine scheduling problems: column generation. INFORMS Journal on Computing (2000) 12:111–124Link, Google Scholar
• Van der Linden S. J. Convex quadratic relaxations and approximation algorithms: a computational study. (2000) . Master's thesis, Department of Operational Research and Management, University of Amsterdam, Amsterdam, The NetherlandsGoogle Scholar