Tight Bounds for Permutation Flow Shop Scheduling

References

• Chakrabarti S., Phillips C., Schulz A., Shmoys D., Stein C., Wein J. Improved scheduling algorithms for Minsum Criteria. Proc. 23rd Internat. Colloquium on Automata, Languages, and Programming (ICALP) (1996) (Springer, Berlin) 646–657Google Scholar
• Chazelle B.The Discrepancy Method: Randomness and Complexity (2000) (Cambridge University Press, Cambridge, UK) Google Scholar
• Chen B., Potts C., Woeginger G., Du D.-Z., Pardalos P. M. A review of machine scheduling: Complexity, algorithms, and approximability. Handbook of Combinatorial Optimization (1998) 3(Kluwer Academic Publishers, Boston) 21–169Google Scholar
• Conway R., Maxwell W., Miller L.Theory of Scheduling (1967) (Addison-Wesley Publishing Co., Reading, MA) Google Scholar
• Czumaj A., Scheideler C. A new algorithmic approach to the general lovasz local lemma with applications to schedulung and satisfiability problems. Proc. 32 ACM Sympos. Theory Comput (STOC) (2000) (ACM Press, New York) 38–47Google Scholar
• Feige U., Scheideler C. Improved bounds for acyclic job shop scheduling. Proc. 30th Annual ACM Sympos. Theory Comput. (STOC) (1998) (ACM Press, New York) 624–633Google Scholar
• Fishkin A., Jansen K., Mastrolilli M. On minimizing average weighted completion time: A PTAS for the job shop problem with release dates. Algorithms and Computation (2003) 2906(Springer, Berlin) 319–328Lecture Notes in Comput. Sci.Crossref, Google Scholar
• Framinan J., Gupta J., Leisten R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. J. Oper. Res. Soc. (2004) 55:1243–1255Crossref, Google Scholar
• Frieze A. On the length of the longest monotone subsequence of a random permutation. Ann. Appl. Probab. (1991) 1(2):301–305Crossref, Google Scholar
• Hall L. A., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off–line and on–line algorithms. Proc. 7th Sympos. Discrete Algorithms (1996) (ACM-SIAM)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) 22:513–544Link, 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., Rinnooy Kan A., Zipkin P. Sequencing and scheduling: Algorithms and complexity. Handbook in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam) 445–522Google Scholar
• Logan B. F., Shepp L. A. A variational problem for random young tableaux. Adv. Math. (1977) 26:206–222Crossref, Google Scholar
• Nawaz M., Enscore E., Ham I. A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. OMEGA Internat. J. Management Sci. (1983) 11:91–95Crossref, Google Scholar
• Nowicki E., Smutnicki C. New results in the worst-case analysis for flow-shop scheduling. Discrete Appl. Math. (1993) 46:21–41Crossref, Google Scholar
• Nowicki E., Smutnicki C. Worst-case analysis of an approximation algorithm for flow-shop scheduling. Oper. Res. Lett. (1989) 8:171–177Crossref, Google Scholar
• Nowicki E., Smutnicki C. Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling. Oper. Res. Lett. (1991) 10:473–480Crossref, Google Scholar
• Potts C., Shmoys D., Williamson D. Permutation vs. nonpermutation flow shop schedules. Oper. Res. Lett. (1991) 10:281–284Crossref, Google Scholar
• Queyranne M. Structure of a simple scheduling polyhedron. Math. Programming Ser. A (1993) 58(2):263–285Crossref, Google Scholar
• Queyranne M., Sviridenko M. Approximation algorithms for shop scheduling problems with minsum objective. J. Scheduling (2002) 5:287–305Crossref, Google Scholar
• Raghavan P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. System Sci. (1988) 37:130–143Crossref, Google Scholar
• Röck H., Schmidt G. Machine aggregation heuristics in shop-scheduling. Methods Oper. Res. (1983) 45:303–314Google Scholar
• Sevast'janov S. On some geometric methods in scheduling theory: A survey. Discrete Appl. Math. (1994) 55:59–82Crossref, Google Scholar
• Schrijver A.Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics) (2003) 24(B)(Springer-Verlag, Berlin) 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
• Smutnicki C. Some results of the worst-case analysis for flow shop scheduling. Eur. J. Oper. Res. (1998) 109:66–87Crossref, Google Scholar
• Sotelo D., Poggi de Aragão M. An approximation algorithm for the permutation flow shop scheduling problem via Erdős-Szekeres Theorem Extensions. (2008) . Working paper, Catholic University of Rio de Janeiro, Rio de JaneiroGoogle Scholar
• Sviridenko M. A note on permutation flow shop problem. Ann. Oper. Res. (2004) 129:247–252Crossref, Google Scholar
• Vershik A. M., Kerov S. V. Asymptotics of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk SSSR (1977) 233:1024–1027Google Scholar