Minimizing Makespan in No-Wait Job Shops

References

• Acampora A., Shah S. Multihop lightwave networks: A comparison of store-and-forward and hot-potato routing. Proc. INFOCOM (1991) Bal Harbour, FL(IEEE, Piscataway, NJ) 10–19Crossref, Google Scholar
• Bartzis C., Caragiannis I., Kaklamanis C., Vergados I. Experimental evaluation of hot-potato routing algorithms on 2-dimensional processor arrays. Proc. Euro-Par (2000) 877–881Crossref, Google Scholar
• Chen B., Potts C., Woeginger G. A review of machine scheduling: Complexity, algorithms and approximability. Handbook of Combinatorial Optimization (1998) 3(Kluwer Academic Publishers, Boston, MA) 21–169Crossref, Google Scholar
• Edwin Cheng T. C., Liu Z. Approximability of two-machine no-wait flowshop scheduling with availability constraints. Oper. Res. Lett. (2003) 31:319–322Crossref, Google Scholar
• Edwin Cheng T. C., Liu Z. 3/2-Approximation for two-machine no-wait flowshop scheduling with availability constraints. Inform. Process. Lett. (2003) 88:161–165Crossref, Google Scholar
• Garey M., Johnson D.Computers and Intractability. A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Co., San Francisco, CA) Google Scholar
• Gilmore P., Gomory R. Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Oper. Res. (1964) 12:655–679Link, Google Scholar
• Glass C., Gupta J. N. D., Potts C. N. Two-machine no-wait flow shop scheduling with missing operations. Math. Oper. Res. (1999) 24:911–924Link, Google Scholar
• Hall L. A. Approximability of flow shop scheduling. Math. Program. (1998) 82:175–190Crossref, Google Scholar
• Hall N., Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. (1996) 44:510–525Link, Google Scholar
• Hillis W.The Connection Machine (1985) (MIT Press, Cambridge, MA) Google Scholar
• Holyer I. The NP-completeness of edge-coloring. SIAM J. Comput. (1981) 10:718–720Crossref, 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
• Kubzin M., Strusevich V. Two-machine flow shop no-wait scheduling with a nonavailability interval. Naval Res. Logist. (2004) 51:613–631Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., Graves S., Kan A. H. G. Rinnooy, Zipkin P. Sequencing and scheduling: Algorithms and complexity. Logistics of Production and Inventory (1993) 4(North Holland, Amsterdam, The Netherlands) 445–522Handbooks in Operations Research and Management ScienceCrossref, Google Scholar
• Macchiaroli R., Mole S., Riemma S. Modelling and optimization of industrial manufacturing processes subject to no-wait constraints. Internat. J. Product. Res. (1999) 37:2585–2607Crossref, Google Scholar
• Mascis A., Pacciarelli D. Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. (2002) 143:498–517Crossref, Google Scholar
• Melnikov L., Vizing V. The edge chromatic number of a directed/mixed multigraph. J. Graph Theory (1999) 31:267–273Crossref, Google Scholar
• Ovacik I., Uzsoy R.Decomposition Methods for Complex Factory Scheduling Problems (1997) (Kluwer, Dordrecht, The Netherlands) Crossref, Google Scholar
• Papadimitriou C. H., Kanellakis P. Flow-shop scheduling with limited temporary storage. J. ACM (1980) 27:533–549Crossref, Google Scholar
• Pyatkin A. (k, l)-Coloring of incidentors of cubic multigraphs (Russian). Diskret. Anal. Issled. Oper. Ser. 1 (2002) 9:49–53Google Scholar
• Raaymakers W., Hoogeveen J. Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. Eur. J. Oper. Res. (2000) 126:131–151Crossref, Google Scholar
• Röck H. The three-machine no-wait flow shop is NP-complete. J. ACM (1984) 31:336–345Crossref, Google Scholar
• Röck H., Schmidt G. Machine aggregation heuristics in shop-scheduling. Methods Oper. Res. (1983) 45:303–314Google Scholar
• Sahni S., Cho Y. Complexity of scheduling shops with no wait in process. Math. Oper. Res. (1979) 4:448–457Link, Google Scholar
• Schuster C., Framinan J. Approximative procedures for no-wait job shop scheduling. Oper. Res. Lett. (2003) 31:308–318Crossref, Google Scholar
• Schuurman P., Woeginger G., Moehring R., Potts C., Schulz A., Woeginger G., Wolsey L. Approximation schemes—A tutorial. Lectures on Scheduling (2005) . ForthcomingGoogle Scholar
• Seitz C. L. The Caltech Mosaic C: An experimental fine-grain multicomputer. Proc. SPAA (1992) San Diego, CA(ACM Press, New York) . Keynote SpeechGoogle Scholar
• Sevastianov S. V., Woeginger G. J. Makespan minimization in open shops: A polynomial time approximation scheme. Math. Program. (1998) 82:191–198Crossref, Google Scholar
• Sidney J. B., Sriskandarajah C. A heuristic for the two-machine no-wait open shop scheduling problem. Naval Res. Logist. (1999) 46:129–145Crossref, Google Scholar
• Sidney J. B., Potts C. N., Sriskandarajah C. A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups. Oper. Res. Lett. (2000) 26:165–173Crossref, Google Scholar
• Smith B. Architecture and applications of the HEP multiprocessor computer system. Proc. 4th Sympos. Real Time Signal Processing IV (1981) 241–248Google Scholar
• Sviridenko M. Makespan minimization in no-wait flow shops: A polynomial time approximation scheme. SIAM J. Discrete Math. (2003) 16:313–322Crossref, Google Scholar
• Szymanski T. An analysis of “hot-potato” routing in a fiber optic packet switched hypercube. Proc. of INFOCOM (1990) San Francisco, CA(ACM Press, New York) 918–925Crossref, Google Scholar
• Vizing V. The coloring of the incidentors and vertices of a directed multigraph. (Russian). Diskret. Anal. Issled. Oper. Ser. 1 (2000) 7:6–16Google Scholar
• Vizing V., Toft B. The coloring of the incidentors and vertices of an undirected multigraph (Russian). Diskret. Anal. Issled. Oper. Ser. 1 (2001) 8:3–14Google Scholar
• Vizing V., Melnikov L., Pyatkin A. On the (k, l)-coloring of incidentors (Russian). Diskret. Anal. Issled. Oper. Ser. 1 (2000) 7:29–37Google 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
• Woeginger G. Inapproximability results for no-wait job shop scheduling. Oper. Res. Lett. (2004) 32:299–397Crossref, Google Scholar