Scheduling and fixed-parameter tractability

详细信息    查看全文

• 作者：Matthias Mnich ; Andreas Wiese
• 关键词：Scheduling ; Fixed ; parameter tractability ; Integer linear programming ; 68W05 ; 90B35
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：154
• 期：1-2
• 页码：533-562
• 全文大小：640 KB
• 参考文献：1.Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proc. FOCS, pp. 32-3 (1999)
  2.Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55-6 (1998)MATH MathSciNet CrossRef
  3.Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844-56 (1995)MATH MathSciNet CrossRef
  4.Bansal, N., Dhamdhere, K.: Minimizing weighted flow time. ACM Trans. Algorithms 3(4), 39 (2007)MathSciNet CrossRef
  5.Bansal, N., Pruhs, K.: The geometry of scheduling. In: Proc. FOCS, pp. 407-14 (2010)
  6.Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: Algorithms-ESA, pp. 145-56. Springer, Berlin (2012)
  7.Bessy, S., Giroudeau, R.: Some parametric complexity results on a coupled-task scheduling problem, personal communication (2013)
  8.Bodlaender, H.L., Fellows, M.R.: \(W[2]\) -hardness of precedence constrained \(K\) -processor scheduling. Oper. Res. Lett. 18(2), 93-7 (1995)MATH MathSciNet CrossRef
  9.Brauner, N., Crama, Y., Grigoriev, A., van de Klundert, J.: A framework for the complexity of high-multiplicity scheduling problems. J. Comb. Optim. 9(3), 313-23 (2005)MATH MathSciNet CrossRef
  10.Chekuri, C., Khanna, S.: Approximation schemes for preemptive weighted flow time. In: Proc. STOC, pp. 297-05 (2002)
  11.Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: Proc. STOC, pp. 84-3 (2001)
  12.Chu, G., Gaspers, S., Narodytska, N., Schutt, A., Walsh, T.: On the complexity of global scheduling constraints under structural restrictions. In: Proc. IJCAI (2013)
  13.Chudak, F.A., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5), 199-04 (1999)MATH MathSciNet CrossRef
  14.Coffman E.G. Jr., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7, 1-7 (1978)
  15.Ebenlendr, T., Kr?ál, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: Proc. SODA, pp. 483-90 (2008)
  16.Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. J. Algorithms 49(1), 175-91 (2003)MATH MathSciNet CrossRef
  17.Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theory Comput. Syst. 50(4), 675-93 (2012)MATH MathSciNet CrossRef
  18.Fellows, M.R., Koblitz, N.: Fixed-parameter complexity and cryptography. In: San Juan, P.R. (ed.) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lecture Notes Comput. Sci., vol. 673, pp. 121-31 (1993)
  19.Fellows, M.R., McCartin, C.: On the parametric complexity of schedules to minimize tardy tasks. Theor. Comput. Sci. 298(2), 317-24 (2003)MATH MathSciNet CrossRef
  20.Friesen, D.K.: Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput. 13, 170-81 (1984)MATH MathSciNet CrossRef
  21.Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)MATH
  22.Goemans, M.X., Rothvo?, T.: Polynomiality for bin packing with a constant number of item types. In: Proc. SODA, pp. 830-39 (2014)
  23.Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 263-69 (1969)
  24.Heinz, S.: Complexity of integer quasiconvex polynomial optimization. J. Complex. 21(4), 543-56 (2005)MATH MathSciNet CrossRef
  25.Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144-62 (1987)MathSciNet CrossRef
  26.Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. Math. Program. 94(2-, Ser. B), 361-74 (2003)MATH MathSciNet CrossRef
  27.Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39-9 (2013)MATH MathSciNet CrossRef
  28.K?ppe, M.: On the complexity of nonlinear mixed-integer optimization. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, vol. 154, pp. 533-57 (2012)
  29.Langston, M.A.: Processor scheduling with improved heuristic algorithms. Ph.D. thesis, Texas A&M University (1981)
  30.Lenstra, J., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. In: Studies in Integer Programming, Ann. Discrete Math., vol. 1, pp. 343-62 (1977)
  31.Lenstra, J.K., Shmoys, D.B., Tardos, é.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1-), 259-71 (1990)MATH MathSciNet CrossRef
  32.Marx, D.: Fixed-parameter tractable scheduling problems. In: Packing and Sched
• 作者单位：Matthias Mnich (1)
  Andreas Wiese (2)
  
  1. Cluster of Excellence MMCI, Campus E1-7, 66123, Saarbrücken, Germany
  2. Max-Planck-Institute for Computer Science, Campus E1-4, 66123, Saarbrücken, Germany
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions—one important example being weighted flow time—and scheduling with rejection. To this end, we identify crucial parameters that determine the problems-complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with \(\mathsf {W[1]}\)-hardness results showing that for smaller sets of parameters the respective problems do not allow fixed-parameter algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx. Keywords Scheduling Fixed-parameter tractability Integer linear programming