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

Computational complexity and algorithms for two scheduling problems under linear constraints

Author

Listed:
  • Kameng Nip

    (Shenzhen University)

  • Peng Xie

    (Xiamen University)

Abstract

This paper considers two different types of scheduling problems under linear constraints. The first is the single-machine scheduling problem with minimizing total completion time, while the second is the no-wait two-machine flow shop scheduling problem with minimizing makespan. For these two problems, a set of jobs is required to be scheduled to one or two machines. In contrast to the classic scheduling problems, the processing times of jobs are not fixed constants and are not predetermined. The decision-maker only knows that they should satisfy a system of given linear constraints. For both problems, the goal is to determine the processing time for each job and find the schedule that minimizes a particular criterion, namely, the total completion time or the makespan. First, we study the computational complexity and show that both the problems under linear constraints are NP-hard. These hardness results significantly differ from their traditional scheduling counterparts, as both of those are solvable in polynomial time. Then we propose polynomial time exact or approximation algorithms for various special cases. By utilizing the existing scheduling algorithms and the properties of linear programming, we demonstrate that both problems are polynomially solvable when the total number of linear constraints is a fixed constant.

Suggested Citation

  • Kameng Nip & Peng Xie, 2024. "Computational complexity and algorithms for two scheduling problems under linear constraints," Journal of Combinatorial Optimization, Springer, vol. 47(4), pages 1-31, May.
    • Handle: RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01122-0
    DOI: 10.1007/s10878-024-01122-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01122-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/s10878-024-01122-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. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    2. Sartaj Sahni & Yookun Cho, 1979. "Complexity of Scheduling Shops with No Wait in Process," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 448-457, November.
    3. Zhenbo Wang & Kameng Nip, 2017. "Bin packing under linear constraints," Journal of Combinatorial Optimization, Springer, vol. 34(4), pages 1198-1209, November.
    4. Nip, Kameng & Wang, Zhenbo & Wang, Zizhuo, 2016. "Scheduling under linear constraints," European Journal of Operational Research, Elsevier, vol. 253(2), pages 290-297.
    5. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    6. Ogryczak, Wlodzimierz & Sliwinski, Tomasz, 2003. "On solving linear programs with the ordered weighted averaging objective," European Journal of Operational Research, Elsevier, vol. 148(1), pages 80-91, July.
    7. Siyun Zhang & Kameng Nip & Zhenbo Wang, 2022. "Related machine scheduling with machine speeds satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1724-1740, October.
    8. Kameng Nip & Tianning Shi & Zhenbo Wang, 2022. "Some graph optimization problems with weights satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 200-225, January.
    9. S. M. Johnson, 1954. "Optimal two‐ and three‐stage production schedules with setup times included," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(1), pages 61-68, March.
    10. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    11. Kameng Nip & Zhenbo Wang & Zizhuo Wang, 2017. "Knapsack with variable weights satisfying linear constraints," Journal of Global Optimization, Springer, vol. 69(3), pages 713-725, 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. Kameng Nip & Zhenbo Wang, 2023. "A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints," Journal of Scheduling, Springer, vol. 26(6), pages 543-558, December.
    2. Abdennour Azerine & Mourad Boudhar & Djamal Rebaine, 2022. "A two-machine no-wait flow shop problem with two competing agents," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 168-199, January.
    3. Siyun Zhang & Kameng Nip & Zhenbo Wang, 2022. "Related machine scheduling with machine speeds satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1724-1740, October.
    4. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    5. Federico Della Croce & Andrea Grosso & Fabio Salassa, 2021. "Minimizing total completion time in the two-machine no-idle no-wait flow shop problem," Journal of Heuristics, Springer, vol. 27(1), pages 159-173, April.
    6. Siyun Zhang & Kameng Nip & Zhenbo Wang, 0. "Related machine scheduling with machine speeds satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    7. Kameng Nip & Tianning Shi & Zhenbo Wang, 2022. "Some graph optimization problems with weights satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 200-225, January.
    8. J.-C. Billaut & F. Della Croce & F. Salassa & V. T’kindt, 2019. "No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths," Journal of Scheduling, Springer, vol. 22(1), pages 59-68, February.
    9. S. S. Panwalkar & Christos Koulamas, 2019. "The evolution of schematic representations of flow shop scheduling problems," Journal of Scheduling, Springer, vol. 22(4), pages 379-391, August.
    10. Shabtay, Dvir & Gilenson, Miri, 2023. "A state-of-the-art survey on multi-scenario scheduling," European Journal of Operational Research, Elsevier, vol. 310(1), pages 3-23.
    11. Levorato, Mario & Figueiredo, Rosa & Frota, Yuri, 2022. "Exact solutions for the two-machine robust flow shop with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 300(1), pages 46-57.
    12. Miri Gilenson & Dvir Shabtay & Liron Yedidsion & Rohit Malshe, 2021. "Scheduling in multi-scenario environment with an agreeable condition on job processing times," Annals of Operations Research, Springer, vol. 307(1), pages 153-173, December.
    13. Celia A. Glass & Yakov M. Shafransky & Vitaly A. Strusevich, 2000. "Scheduling for parallel dedicated machines with a single server," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(4), pages 304-328, June.
    14. Matthias Bultmann & Sigrid Knust & Stefan Waldherr, 2018. "Flow shop scheduling with flexible processing times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 809-829, July.
    15. Christoph Schuster, 2006. "No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(3), pages 473-491, July.
    16. Raaymakers, W. H. M. & Hoogeveen, J. A., 2000. "Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing," European Journal of Operational Research, Elsevier, vol. 126(1), pages 131-151, October.
    17. Kravchenko, Svetlana A., 1998. "A polynomial algorithm for a two-machine no-wait job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 106(1), pages 101-107, April.
    18. Christoph Hertrich & Christian Weiß & Heiner Ackermann & Sandy Heydrich & Sven O. Krumke, 2020. "Scheduling a proportionate flow shop of batching machines," Journal of Scheduling, Springer, vol. 23(5), pages 575-593, October.
    19. Abdelhakim AitZai & Brahim Benmedjdoub & Mourad Boudhar, 2016. "Branch-and-bound and PSO algorithms for no-wait job shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(3), pages 679-688, June.
    20. Kameng Nip & Zhenbo Wang & Fabrice Talla Nobibon & Roel Leus, 2015. "A combination of flow shop scheduling and the shortest path problem," Journal of Combinatorial Optimization, Springer, vol. 29(1), pages 36-52, January.

    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:4:d:10.1007_s10878-024-01122-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.