Single-Machine Scheduling Problems with Generalized Preemption

References

• Allahverdi A., Gupta J. N. D., Aldowaisan T. A review of scheduling research involving setup considerations. Omega (1999) 27:219–239Crossref, Google Scholar
• Baptiste P. An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Oper. Res. Lett. (1999) 24(4):175–180Crossref, Google Scholar
• Baptiste B., Peridy L., Pinson E. A branch and bound to minimize the number of late jobs on a single machine with release time contraints. Eur. J. Oper. Res. (2003) 144:1–11Crossref, Google Scholar
• Caprara A., Salazar J. J. Separating lifted odd-hole inequalities to solve the index selection problem. Discrete Appl. Math. (1999) 92:111–134Crossref, Google Scholar
• Cho D. C., Johnson E. L., Padberg M. W., Rao M. R. On the uncapacitated plant location problem. I: Valid inequalities and facets. Math. Oper. Res. (1983) 8:579–589Link, Google Scholar
• Dietrich B., Forrest J. J., Dietrich B., Vohra R. V. A column generation approach for combinatorial auctions. Mathematics of the Internet: E-Auctions and Markets. The IMA Volumes in Mathematics and Its Applications (2002) 127(Springer-Verlag, New York) 15–26Crossref, Google Scholar
• Goemans M. X., Wein J. M., Williamson D. P. A 1:47-Approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. (2000) 26:149–154Crossref, Google Scholar
• Hopp W. J., Spearman M. L.Factory Physics: Foundations of Manufacturing Management (2000) (McGraw-Hill, New York) Google Scholar
• Julien F. M., Magazine M. J., Hall N. G. Generalized preeemption models for single-machine dynamic scheduling problems. IIE Trans. (1997) 29:359–372Crossref, Google Scholar
• Lawler E. L. A dynamic programming algorithm for the preemptive scheduling of a single machine to minimize the number of late jobs. Ann. Oper. Res. (1990) 26:125–133Crossref, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems. Ann. Discrete Math. (1977) 1:343–362Crossref, Google Scholar
• Liu Z., Cheng T. C. E. Minimizing total completion time subject to job release dates and preemption penalties. J. Sched. (2004) 7:313–327Crossref, Google Scholar
• Martin P., Shmoys D. B., Cunningham W. H., McCormick S. T., Queyranne M. A new approach to computing optimal schedules for the job-shop scheduling problem. Proc. 5th Internat. IPCO Conf. Integer Programing Combinatorial Optimization, Lecture Notes in Computer Science (1996) 1084(Springer-Verlag, London) 389–403Crossref, Google Scholar
• Pinedo M.Scheduling: Theory, Algorithms, and Systems (1995) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Simons B. A fast algorithm for single processor scheduling. Proc. 19th Annual Symp. Found. Comput. Sci., FOCS '78 (1978) (Institute of Electrical and Electronics Engineers, Washington, D.C.) 246–252Crossref, Google Scholar
• Zdrzalka S. Preemptive scheduling with release dates, delivery times, and sequence independent setup times. Eur. J. Oper. Res. (1994) 76:60–71Crossref, Google Scholar