Determining Process Capacity: Intractability and Efficient Special Cases

References

• Alfonsin JLR (2001) Perfect Graphs (Wiley, Hoboken, NJ).Google Scholar
• Anupindi R, Deshmukh S, Van Mieghem JA, Zemel E (2014) Managing Business Process Flows, 3rd ed. (Pearson, London).Google Scholar
• Bellare M, Goldreich O, Sudan M (1998) Free bits, PCPs, and nonapproximability—Towards tight results. SIAM J. Comput. 27(3):804–915.Crossref, Google Scholar
• Berge C (1989) Hypergraphs: Combinatorics of Finite Sets (North-Holland, Amsterdam).Google Scholar
• Bollóbas B (2002) Modern Graph Theory. Axler S, Gehring FW, Ribet KA, eds. Graduate Texts in Mathematics (Springer, New York).Google Scholar
• Brauner N (2008) Identical part production in cyclic robotic cells: Concepts, overview and open questions. Discrete Appl. Math. 156(13):2480–2492.Crossref, Google Scholar
• Cachon G, Terwiesch C (2013) Matching Supply with Demand, 3rd ed. (McGraw-Hill, New York).Google Scholar
• Chudnovsky M, Roberson N, Seymour PD, Thomas R (2006) The strong perfect graph theorem. Ann. Math. 164(1):51–229.Crossref, Google Scholar
• Chudnovsky M, Cornuéjols G, Liu X, Seymour P, Vusković K (2005) Recognizing Berge graphs. Combinatorica 25(2):143–186.Crossref, Google Scholar
• Dawande M, Geismar HN, Sethi SP, Sriskandarajah C (2007) Throughput Optimization in Robotic Cells (Springer, New York).Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, New York).Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Crossref, Google Scholar
• Gurvich I, Van Mieghem JA (2015) Collaboration and multitasking in networks: Architectures, bottlenecks, and capacity. Manufacturing Service Oper. Management 17(1):16–33.Link, Google Scholar
• Gurvich I, Van Mieghem JA (2018) Collaboration and multitasking in networks: Prioritization and achievable capacity. Management Sci. 64(5):2390–2406.Link, Google Scholar
• Gurvich I, O’Leary KJ, Wang L, Van Mieghem JA (2018) Collaboration, interruptions and changeover times: Workflow model and empirical study of hospitalist charting. Working paper, Cornell University, Ithaca, NY.Google Scholar
• Gurvich I, Van Mieghem JA, Wang L, Soulakis ND (2017) How digital and physical care team interaction affect processing times: A case study of hospitalists. J. Case Reports Stud. 5(6):606.Google Scholar
• Heizer JH, Render B (2014) Operations Management, 11th ed. (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Kampmeyer T (2006) Cyclic scheduling problems. PhD thesis, University of Osnabruck, Osnabruck, Germany.Google Scholar
• Kennedy WS (2011) Fractional edge and total colouring. PhD thesis, McGill University, Quebec.Google Scholar
• Larsen M, Propp J, Ullman D (1995) The fractional chromatic number of Mycielski’s graphs. J. Graph Theory 19(3):411–416.Crossref, Google Scholar
• Levner E, Kats V (1998) A parametric critical path problem and an application for cyclic scheduling. Discrete Appl. Math. 87(1):149–158.Crossref, Google Scholar
• Levner E, Kats V, de Pablo DAL, Cheng T (2010) Complexity of cyclic scheduling problems: A state-of-the-art survey. Comput. Indust. Engrg. 59(2):352–361.Crossref, Google Scholar
• Lovász L (1972) Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2(3):253–267.Crossref, Google Scholar
• Lund C, Yannakakis M (1994) On the hardness of approximating minimization problems. J. ACM 41(5):960–981.Crossref, Google Scholar
• McCormick ST, Rao U (1994) Some complexity results in cyclic scheduling. Math. Comput. Model. 20(2):107–122.Crossref, Google Scholar
• McCormick ST, Pinedo ML, Shenker S, Wolf B (1989) Sequencing in an assembly line with blocking to minimize cycle time. Oper. Res. 37(6):925–935.Link, Google Scholar
• Roundy R (1992) Cyclic schedules for job shops with identical jobs. Math. Oper. Res. 17(4):842–865.Link, Google Scholar
• Rudin W (1976) Principles of Mathematical Analysis. Martin WT, Spanier EH, Springer G, Davis PJ, eds. International Series in Pure and Applied Mathematics (McGraw-Hill, New York).Google Scholar
• Scheinerman E, Ullman D (2013) Fractional Graph Theory: A Rational Approach to the Theory of Graphs (Dover, New York).Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming. Graham RL, Lenstra JK, Tarjan RE, eds. Wiley Series in Discrete Mathematics and Optimization (Wiley, Hoboken, NJ).Google Scholar
• Stevenson WJ (2014) Operations Management: Theory and Practice, 12th ed. (McGraw-Hill Irwin, New York).Google Scholar