IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v47y2024i2d10.1007_s10878-024-01108-y.html
   My bibliography  Save this article

EPTAS for parallel identical machine scheduling with time restrictions

Author

Listed:
  • G. Jaykrishnan

    (The Technion)

  • Asaf Levin

    (The Technion)

Abstract

We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS.

Suggested Citation

  • G. Jaykrishnan & Asaf Levin, 2024. "EPTAS for parallel identical machine scheduling with time restrictions," Journal of Combinatorial Optimization, Springer, vol. 47(2), pages 1-21, March.
    • Handle: RePEc:spr:jcomop:v:47:y:2024:i:2:d:10.1007_s10878-024-01108-y
    DOI: 10.1007/s10878-024-01108-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01108-y
    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/s10878-024-01108-y?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. Rachid Benmansour & Oliver Braun & Saïd Hanafi, 2019. "The single-processor scheduling problem with time restrictions: complexity and related problems," Journal of Scheduling, Springer, vol. 22(4), pages 465-471, August.
    2. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    3. Dell'Amico, Mauro & Iori, Manuel & Martello, Silvano & Monaci, Michele, 2006. "Lower bounds and heuristic algorithms for the ki-partitioning problem," European Journal of Operational Research, Elsevier, vol. 171(3), pages 725-742, June.
    4. Oliver Braun & Fan Chung & Ron Graham, 2016. "Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 531-540, March.
    5. Klaus Jansen & Kim-Manuel Klein & José Verschae, 2020. "Closing the Gap for Makespan Scheduling via Sparsification Techniques," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1371-1392, November.
    Full references (including those not matched with items on IDEAS)

    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. Ruiqing Sun, 2024. "Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines," Journal of Combinatorial Optimization, Springer, vol. 47(3), pages 1-16, April.
    2. 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.
    3. 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.
    4. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    5. 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.
    6. Danny Nguyen & Igor Pak, 2020. "The Computational Complexity of Integer Programming with Alternations," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 191-204, February.
    7. Sascha Kurz & Nikolas Tautenhahn, 2013. "On Dedekind’s problem for complete simple games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 411-437, May.
    8. 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.
    9. Katrin Halbig & Lukas Hümbs & Florian Rösel & Lars Schewe & Dieter Weninger, 2024. "Computing Optimality Certificates for Convex Mixed-Integer Nonlinear Problems," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1579-1610, December.
    10. Herbert E. Scarf & David F. Shallcross, 2008. "The Frobenius Problem and Maximal Lattice Free Bodies," Palgrave Macmillan Books, in: Zaifu Yang (ed.), Herbert Scarf’s Contributions to Economics, Game Theory and Operations Research, chapter 7, pages 149-153, Palgrave Macmillan.
    11. Elhedhli, Samir & Naoum-Sawaya, Joe, 2015. "Improved branching disjunctions for branch-and-bound: An analytic center approach," European Journal of Operational Research, Elsevier, vol. 247(1), pages 37-45.
    12. Xiaofei Liu & Weidong Li & Yaoyu Zhu, 2021. "Single Machine Vector Scheduling with General Penalties," Mathematics, MDPI, vol. 9(16), pages 1-16, August.
    13. Mauro Dell’Amico & Simone Falavigna & Manuel Iori, 2015. "Optimization of a Real-World Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 49(2), pages 402-419, May.
    14. Danny Hermelin & Matthias Mnich & Simon Omlor, 2024. "Serial batching to minimize the weighted number of tardy jobs," Journal of Scheduling, Springer, vol. 27(6), pages 545-556, December.
    15. Karen Aardal & Cor A. J. Hurkens & Arjen K. Lenstra, 2000. "Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables," Mathematics of Operations Research, INFORMS, vol. 25(3), pages 427-442, August.
    16. Guojun Hu & Pengxiang Pan & Suding Liu & Ping Yang & Runtao Xie, 2024. "The prize-collecting single machine scheduling with bounds and penalties," Journal of Combinatorial Optimization, Springer, vol. 48(2), pages 1-13, September.
    17. Ariel D Procaccia & Michal Feldmany & Jeffrey S Rosenschein, 2007. "Approximability and Inapproximability of Dodgson and Young Elections," Levine's Bibliography 122247000000001616, UCLA Department of Economics.
    18. Klabjan, Diego, 2007. "Subadditive approaches in integer programming," European Journal of Operational Research, Elsevier, vol. 183(2), pages 525-545, December.
    19. Rainer Kolisch & Erik Demeulemeester & Rubén Ruiz Garcia & Vincent T’Kindt & Jan Węglarz, 2016. "Editorial “Project Management and Scheduling”," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 279-281, March.
    20. Alexander Bockmayr & Friedrich Eisenbrand, 2001. "Cutting Planes and the Elementary Closure in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 26(2), pages 304-312, May.

    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:jcomop:v:47:y:2024:i:2:d:10.1007_s10878-024-01108-y. 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.