An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems

References

• Anderson E. J., Glass C. A., Potts C. N., Aarts E., Lenstra J. K. Machine scheduling. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 361–414Google Scholar
• Belouadah H. Scheduling to minimize total cost. (1985) . M.Sc. thesis, University of Keele, Staffordshire, UKGoogle Scholar
• Belouadah H., Posner M. E., Potts C. N. Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Appl. Math. (1992) 36:213–231Crossref, Google Scholar
• Bianco L., Ricciardelli S. Scheduling of a single machine to minimize total weighted completion time subject to release dates. Naval Res. Logist. Quart. (1982) 29:151–167Crossref, Google Scholar
• Cavalcante C. C. B., Carvalho de Sousa C., Savelsbergh M. W. P., Wang Y., Wolsey L. A. Scheduling projects with labour constraints. Discrete Appl. Math. (2001) 112:27–52Crossref, Google Scholar
• Chakrabarti S., Phillips C., Schulz A. S., Shmoys D. B., Stein C., Wein J. Improved bounds on relaxations of a parallel machine scheduling problem. J. Combin. Optim. (1998) 1:413–426Crossref, Google Scholar
• Chandra R. On n/1/F̄ dynamic deterministic systems. Naval Res. Logist. Quart. (1979) 26:537–544Crossref, Google Scholar
• Chekuri C., Motwani R., Natarajan B., Stein C. Approximation techniques for average completion time scheduling. SIAM J. Comput. (2000) 31Google Scholar
• De Sousa J. P., Wolsey L. A. A time-indexed formulation of non-preemptive single-machine scheduling problems. Math. Programming (1992) 54:353–367Crossref, Google Scholar
• Dessouky M. I., Deogun J. S. Sequencing jobs with unequal ready times to minimize mean flow-time. SIAM J. Comput. (1981) 10:192–202Crossref, Google Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. (1990) 26:255–270Crossref, Google Scholar
• Goemans M. X. A supermodular relaxation for scheduling with release dates. Proc. 5th MPS Conf. on Integer Programming and Combin. Optim., LNCS (1996) 1084(Springer-Verlag, Berlin, Germany) 288–300Crossref, Google Scholar
• Goemans M. X. Improved approximation algorithms for scheduling with release dates. Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, LNCS (1997) 1099(Springer-Verlag, Berlin, Germany) 591–598Google Scholar
• Goemans M. X., Queyranne M., Schulz A., Skutella M., Wang Y. Single machine scheduling with release dates. SIAM J. Discrete Math. (2002) 15:165–192Crossref, Google Scholar
• Hall L. A., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line algorithms. Proc. 7th ACM-SIAM Sympos. Discrete Algorithms (1996) (ACM, New York) 142–151Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 3:513–544Link, Google Scholar
• Hariri A. M. A., Potts C. N. An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Appl. Math. (1983) 5:99–109Crossref, Google Scholar
• Kallrath J., Wilson J. M.Business Optimisation Using Mathematical Programming (1997) (Macmillan Publishers, Hampshire, UK) Google Scholar
• Kellerer H., Tautenhahn T., Woeginger G. J. Approximability and nonapproximability results for minimizing total flow-time on a single machine. SIAM J. Comput. (1999) 28:1155–1166Crossref, Google Scholar
• Phillips C., Stein C., Wein J. Minimizing average completion time in the presence of release dates. Math. Programming B (1998) 82:199–224Crossref, Google Scholar
• Posner M. E. Minimizing weighted completion times with deadlines. Oper. Res. (1985) 33:562–574Link, Google Scholar
• Potts C. N., van Wassenhove L. N. An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. Eur. J. Oper. Res. (1983) 12:379–387Crossref, Google Scholar
• Queyranne M. Structure of a simple scheduling polyhedron. Math. Programming (1993) 58:263–285Crossref, Google Scholar
• Queyranne M., Schulz A. S. Polyhedral approaches to machine scheduling. (1994) . Technical report 408/1994, Institut für Mathematik, Technische Universität Berlin, Berlin, GermanyGoogle Scholar
• Rinaldi G., Sassano A. On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution. (1977) . Tech. report R.77–24, Istituto di Automatica, Università di Roma, Rome, ItalyGoogle Scholar
• Schulz A. S. Scheduling to minimize total weighted completion time: Performance guarantees of LP based heuristics and lower bounds. Proc. 5th MPS Conf. Integer Programming Combin. Optim., LNCS (1996) 1084(Springer-Verlag, Berlin, Germany) 301–315Crossref, Google Scholar
• Schulz A. S., Skutella M., Burkard R., Woeginger G. Scheduling LPs bear probabilities: Randomized approximations for min-sum criteria. Algorithms–ESA'97, LNCS (1997a) 1284(Springer, Berlin, Germany) 416–429Proc. 5th Annual Eur. Sympos. AlgorithmsCrossref, 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, LNCS (1997b) 1269(Springer, Berlin, Germany) 119–133Proc. Internat. Workshop RANDOM'97Crossref, Google Scholar
• Uma R. N., Wein J., Williamson D. P. On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems. (2003) . Technical report, Department of Computer Science, University of Texas at Dallas, Richardson, TX. (Preliminary version appeared in IPCO: 6th Integer Programming Combin. Optim. Conf. 1998.)Google Scholar
• van den Akker M. LP-based solution methods for single-machine scheduling problems. (1994) . Ph.D. thesis, Department of Mathematics and Computing Science, Eindhoven Univ. of Technology, Eindhoven, The NetherlandsGoogle Scholar
• van den Akker M., Hurkens C. A. J., Savelsbergh M. W. P. A time-indexed formulation for single-machine scheduling problems: Column generation. INFORMS J. Comput. (2000) 12:111–124Link, Google Scholar
• van den Akker M., Van Hoesel C. P. M., Savelsbergh M. W. P. A polyhedral approach to single-machine scheduling problems. Math. Programming (1999) 85:541–572Crossref, Google Scholar
• Wang Y. Bicriteria job scheduling with release dates. (1996) . Tech. Rep., Max-Planck-Institut für Informatik, Saarbrücken, GermanyGoogle Scholar
• Wolsey L. A. Mixed integer programming formulations for production planning and scheduling problems. 12th Internat. Sympos. Math. Programming (1985) (MIT, Cambridge, MA) Google Scholar