IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v21y2018i5d10.1007_s10951-017-0550-0.html
   My bibliography  Save this article

Scheduling meets n-fold integer programming

Author

Listed:
  • Dušan Knop

    (Charles University)

  • Martin Koutecký

    (Charles University)

Abstract

Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In this paper, we continue this study and show that several additional cases of fundamental scheduling problems are fixed-parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where $$p_{\max }$$ p max is the maximum processing time of a job and $$w_{\max }$$ w max is the maximum weight of a job: Makespan minimization on uniformly related machines ( $$Q||C_{\max }$$ Q | | C max ) parameterized by $$p_{\max }$$ p max , Makespan minimization on unrelated machines ( $$R||C_{\max }$$ R | | C max ) parameterized by $$p_{\max }$$ p max and the number of kinds of machines (defined later), Sum of weighted completion times minimization on unrelated machines ( $$R||\sum w_jC_j$$ R | | ∑ w j C j ) parameterized by $$p_{\max }+w_{\max }$$ p max + w max and the number of kinds of machines, The same problem, $$R||\sum w_jC_j$$ R | | ∑ w j C j , parameterized by the number of distinct job times and the number of machines.

Suggested Citation

  • Dušan Knop & Martin Koutecký, 2018. "Scheduling meets n-fold integer programming," Journal of Scheduling, Springer, vol. 21(5), pages 493-503, October.
  • Handle: RePEc:spr:jsched:v:21:y:2018:i:5:d:10.1007_s10951-017-0550-0
    DOI: 10.1007/s10951-017-0550-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-017-0550-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10951-017-0550-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    2. W. A. Horn, 1973. "Technical Note—Minimizing Average Flow Time with Parallel Machines," Operations Research, INFORMS, vol. 21(3), pages 846-847, June.
    3. Yuichi Asahiro & Jesper Jansson & Eiji Miyano & Hirotaka Ono & Kouhei Zenmyo, 2011. "Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree," Journal of Combinatorial Optimization, Springer, vol. 22(1), pages 78-96, July.
    4. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    5. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    2. Danny Hermelin & Shlomo Karhi & Michael Pinedo & Dvir Shabtay, 2021. "New algorithms for minimizing the weighted number of tardy jobs on a single machine," Annals of Operations Research, Springer, vol. 298(1), pages 271-287, March.
    3. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    4. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    5. Hermelin, Danny & Pinedo, Michael & Shabtay, Dvir & Talmon, Nimrod, 2019. "On the parameterized tractability of single machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 273(1), pages 67-73.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ravindran Vijayalakshmi, Vipin & Schröder, Marc & Tamir, Tami, 2024. "Minimizing total completion time with machine-dependent priority lists," European Journal of Operational Research, Elsevier, vol. 315(3), pages 844-854.
    2. Wegel, Sebastian & Ivanov, Anton & Lenz, Ralf & Volling, Thomas, 2024. "Scheduling of parallel continuous annealing lines with alternative processing modes to optimize efficiency under tardiness constraints," European Journal of Operational Research, Elsevier, vol. 316(1), pages 282-294.
    3. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    4. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    5. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    6. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    7. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    8. Shahvari, Omid & Logendran, Rasaratnam, 2016. "Hybrid flow shop batching and scheduling with a bi-criteria objective," International Journal of Production Economics, Elsevier, vol. 179(C), pages 239-258.
    9. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.
    10. Hinder, Oliver & Mason, Andrew J., 2017. "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness," European Journal of Operational Research, Elsevier, vol. 262(2), pages 411-423.
    11. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    12. Hongjun Wei & Jinjiang Yuan & Yuan Gao, 2019. "Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time," Mathematics, MDPI, vol. 7(9), pages 1-10, September.
    13. Han Hoogeveen & Petra Schuurman & Gerhard J. Woeginger, 2001. "Non-Approximability Results for Scheduling Problems with Minsum Criteria," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 157-168, May.
    14. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    15. Dirk Briskorn & Konrad Stephan & Nils Boysen, 2022. "Minimizing the makespan on a single machine subject to modular setups," Journal of Scheduling, Springer, vol. 25(1), pages 125-137, February.
    16. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    17. Jaykrishnan, G. & Levin, Asaf, 2024. "Scheduling with cardinality dependent unavailability periods," European Journal of Operational Research, Elsevier, vol. 316(2), pages 443-458.
    18. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    19. Zigao Wu & Shaohua Yu & Tiancheng Li, 2019. "A Meta-Model-Based Multi-Objective Evolutionary Approach to Robust Job Shop Scheduling," Mathematics, MDPI, vol. 7(6), pages 1-19, June.
    20. Morais, Rafael & Bulhões, Teobaldo & Subramanian, Anand, 2024. "Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates," European Journal of Operational Research, Elsevier, vol. 315(2), pages 442-453.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:21:y:2018:i:5:d:10.1007_s10951-017-0550-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.