Job Shop Scheduling with Unit Processing Times

References

• Akers S. B. A graphical approach to production scheduling problems. Oper. Res. (1956) 4:244–245Link, Google Scholar
• Alon N., Spencer J.The Probabilistic Method (2000) (John Wiley & Sons, New York) Crossref, Google Scholar
• Anderson E. J., Jayram T. S., Kimbrel T. Tighter bounds on preemptive job shop scheduling with two machines. Computing (2001) 67:83–90Crossref, Google Scholar
• Baptiste P., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M. Structural properties of preemptive schedules. . ForthcomingGoogle Scholar
• Czumaj A., Scheideler C. A new algorithmic approach to the general Lovász local lemma with applications to scheduling and satisfiability problems. Proc. 32nd ACM Sympos. Theory Comput. (STOC) (2000) Portland, ORGoogle Scholar
• Feige U., Scheideler C. Improved bounds for acyclic job shop scheduling. Combinatorica (2002) 22(3):361–399Crossref, Google Scholar
• Goldberg L. A., Paterson M., Srinivasan A., Sweedyk E. Better approximation guarantees for job-shop scheduling. SIAM J. Discrete Math. (2001) 14:67–92Crossref, Google Scholar
• Gonnet G. Expected length of the longest probe sequence in hash code searching. J. Association Comput. Machinery (1981) 28(2):289–304Crossref, Google Scholar
• Gonzalez T., Sahni S. Flowshop and jobshop schedules: Complexity and approximation. Oper. Res. (1978) 26:36–52Link, Google Scholar
• Jansen K., Solis-Oba R., Sviridenko M. Makespan minimization in job shops: A linear time approximation scheme. SIAM J. Discrete Math. (2003) 16:288–300Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., Graves S. C., Rinnooy Kan A. H. G., Zipkin P. H. Sequencing and scheduling: Algorithms and complexity. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam, The Netherlands)445–522Crossref, Google Scholar
• Leighton F. T., Maggs B., Rao S. Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica (1994) 14:167–186Crossref, Google Scholar
• Leighton F. T., Maggs B. M., Richa A. W. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica (1999) 19:375–401Crossref, Google Scholar
• Raab M., Steger A. Balls into bins—A simple and tight analysis. Randomization and Approximation Techniques in Computer Science (RANDOM). Lecture Notes in Computer Science (1998) 1518(Springer, Berlin, Germany) 159–170Barcelona, SpainCrossref, Google Scholar
• Sevastianov S. Bounding algorithm for the routing problem with arbitrary paths and alternative servers. Cybernetics (1986) 22:773–780Crossref, Google Scholar
• Sevastianov S. On some geometric methods in scheduling theory: A survey. Discrete Appl. Math. (1994) 55(1):59–82Crossref, Google Scholar
• Sevastianov S. V., Woeginger G. J. Makespan minimization in preemptive two machine job shops. Computing (1998) 60:73–79Crossref, Google Scholar
• Shmoys D., Stein C., Wein J. Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. (1994) 23(3):617–632Crossref, Google Scholar
• Sotskov Y., Shakhlevich N. NP-hardness of shop-scheduling problems with three jobs. Discrete Appl. Math. (1995) 59(3):237–266Crossref, Google Scholar
• Williamson D. P., Hall L. A., Hoogeveen J. A., Hurkens C. A. J., Lenstra J. K., Sevastianov S. V., Shmoys D. B. Short shop schedules. Oper. Res. (1997) 45:288–294Link, Google Scholar