Khung Phân Tích Độ Phức Tạp cho Các Vấn Đề Lập Lịch Độ Đa Dạng Cao

A. Bar-Noy, R. Bhatia, J.S. Naor, and B. Schiber, “Minimizing service and operation costs of periodic scheduling,” Mathematics of Operations Research, vol. 27, pp. 518–544, 2002. N. Brauner and Y. Crama, “The maximum deviation just-in-time scheduling problem,” Discrete Applied Mathematics, vol. 134, pp. 25–50, 2004. N. Brauner, Y. Crama, A. Grigoriev, and J. van de Klundert, “On the complexity of high-multiplicity scheduling problems,” University of Liège, Liège, Belgium, Working paper GEMME 0110, 2001. N. Brauner, G. Finke, and W. Kubiak, “Complexity of one-cycle robotic flow-shops,” Journal of Scheduling, vol. 6, pp. 355–371, 2003. J.J. Clifford and M. E. Posner, “High multiplicity in earliness-tardiness scheduling,” Operations Research, vol. 48, pp. 788–800, 2000. J.J. Clifford and M.E. Posner, “Parallel machine scheduling with high multiplicity,” Mathematical Programming, vol. 89, pp. 359–383, 2001. S.S. Cosmadakis and C.H. Papadimitriou, “The traveling salesman problem with many visits to few cities,” SIAM Journal on Computing, vol. 13, pp. 99–108, 1984. M.E. Dyer, “The complexity of vertex enumeration methods,” Mathematics of Operations Research, vol. 8, pp. 381–402, 1983. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979. F. Granot and J. Skorin-Kapov, “On polynomial solvability of the high multiplicity total weighted tardiness problem,” Discrete Applied Mathematics, vol. 41, pp. 139–146, 1993. A. Grigoriev, “High Multiplicity Scheduling Problems,” Maastricht University, The Netherlands, Doctoral thesis, 2003. D.S. Hochbaum and R. Shamir, “Minimizing the number of tardy job units under release time constraints,” Discrete Applied Mathematics, vol. 28, pp. 45–57, 1990. D.S. Hochbaum and R. Shamir, “Strongly polynomial algorithms for the high multiplicity scheduling problem,” Operations Research, vol. 39, pp. 648–653, 1991. D.S. Hochbaum, R. Shamir, and J.G. Shanthikumar, “A polynomial algorithm for an integer quadratic nonseparable transportation problem,” Mathematical Programming, vol. 55, pp. 359–376, 1992. J. Hurink and S. Knust, “Makespan minimization for flow-shop problems with transportation times and a single robot,” Discrete Applied Mathematics, vol. 112, pp. 199–216, 2001. D.S. Johnson, M. Yannakakis, and C.H. Papadimitriou, “On generating all maximal independent sets,” Information Processing Letters, vol. 27, pp. 119–123, 1988. W. Kubiak and S.P. Sethi, “A note on “Level schedules for mixed-model assembly lines in just-in-time production systems,” Management Science, vol. 37, pp. 121–122, 1991. W. Kubiak and S.P. Sethi, “Optimal just-in-time schedules for flexible transfer lines,” International Journal of Flexible Manufacturing Systems, vol. 6, pp. 137–154, 1994. E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, “Generating all maximal independent sets: NP-hardness and polynomial-time algorithms,” SIAM Journal on Computing, vol. 9, pp. 558–565, 1980. S.T. McCormick, S.R. Smallwood, and F.C.R. Spieksma, “A polynomial algorithm for multiprocessor scheduling with two job lengths,” Mathematics of Operations Research, vol. 26, pp. 31–49, 2001. J. Miltenburg, “Level schedules for mixed-model assembly lines in just-in-time production systems,” Management Science, vol. 35, pp. 192–207, 1989. A. Munier and F. Sourd, “Scheduling chains on a single machine with non-negative time-lags,” Mathematical Methods of Operations Research, vol. 57, pp. 111–123, 2003. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall: Englewood Cliffs, N.J., 1982. M. Pinedo, Scheduling: Theory, Algorithms and Systems, Prentice Hall: Englewood Cliffs, N.J., 1995. M.E. Posner, “The complexity of earliness and tardiness scheduling problems under id-encoding,” New York University, New York, U.S.A, Working Paper 85–70, 1985. H.N. Psaraftis, “A dynamic programming approach for sequencing groups of identical jobs,” Operations Research, vol. 28, pp. 1347–1359, 1980. M. Rothkopf, “The travelling salesman problem: On the reduction of certain large problems to smaller ones,” Operations Research, vol. 14, pp. 532–533, 1966. G. Steiner and J.S. Yeomans, “Level schedules for mixed-model, just-in-time processes,” Management Science, vol. 39, pp. 728–735, 1993.