Abstract
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 W[1]-hardness results showing that for smaller sets of parameters the respective problems do not allow FPT-algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Processing Time
- Schedule Problem
- Completion Time
- Polynomial Time Approximation Scheme
- Unrelated Parallel Machine
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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 1999, pp. 32–43 (1999)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM 34, 144–162 (1987)
Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theory Comput. Syst. 50(4), 675–693 (2012)
Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46(1-3), 259–271 (1990)
Marx, D.: Fixed-parameter tractable scheduling problems. In: Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091), vol. 1, p. 86 (2011)
Bansal, N., Pruhs, K.: The geometry of scheduling. In: Proc. FOCS 2010, pp. 407–414 (2010)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 263–269 (1969)
Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7, 1–17 (1978)
Friesen, D.K.: Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput. 13, 170–181 (1984)
Langston, M.A.: Processor scheduling with improved heuristic algorithms. PhD thesis, Texas A&M University (1981)
Sahni, S.: Algorithms for scheduling independent tasks. J. ACM 23, 116–127 (1976)
Ebenlendr, T., Krčál, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: Proc. SODA 2008, pp. 483–490 (2008)
Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Mathematical Programming 62(5), 461–474 (1993)
Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(4), 1318–1341 (2012)
Bansal, N., Dhamdhere, K.: Minimizing weighted flow time. ACM Trans. Algorithms 3(4) (November 2007)
Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: Proc. STOC 2001, pp. 84–93 (2001)
Chekuri, C., Khanna, S.: Approximation schemes for preemptive weighted flow time. In: Proc. STOC 2002, pp. 297–305 (2002)
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–191 (2003)
Sviridenko, M., Wiese, A.: Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 387–398. Springer, Heidelberg (2013)
Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. Math. Program. 94(2-3, Ser. B), 361–374 (2003)
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–323 (2005)
Bodlaender, H.L., Fellows, M.R.: W[2]-hardness of precedence constrained K-processor scheduling. Oper. Res. Lett. 18(2), 93–97 (1995)
Fellows, M.R., McCartin, C.: On the parametric complexity of schedules to minimize tardy tasks. Theoret. Comput. Sci. 298(2), 317–324 (2003)
Marx, D., Schlotter, I.: Stable assignment with couples: Parameterized complexity and local search. Discr. Optimization 8(1), 25–40 (2011)
Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55–66 (1998)
Chu, G., Gaspers, S., Narodytska, N., Schutt, A., Walsh, T.: On the complexity of global scheduling constraints under structural restrictions. In: Proc. IJCAI 2013 (2013)
Heinz, S.: Complexity of integer quasiconvex polynomial optimization. J. Complexity 21(4), 543–556 (2005)
Köppe, M.: On the complexity of nonlinear mixed-integer optimization. In: Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol. 154, pp. 533–557 (2012)
Goemans, M.X., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: Proc. SODA 2014 (to appear, 2014)
Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. System Sci. 79(1), 39–49 (2013)
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–204 (1999)
Lenstra, J., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. In: Studies in Integer Programming. Ann. Discrete Math, vol. 1, pp. 343–362 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Mnich, M., Wiese, A. (2014). Scheduling and Fixed-Parameter Tractability. In: Lee, J., Vygen, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2014. Lecture Notes in Computer Science, vol 8494. Springer, Cham. https://doi.org/10.1007/978-3-319-07557-0_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-07557-0_32
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07556-3
Online ISBN: 978-3-319-07557-0
eBook Packages: Computer ScienceComputer Science (R0)