Computational complexity and algorithms for two scheduling problems under linear constraints
Author
Abstract
Suggested Citation
DOI: 10.1007/s10878-024-01122-0
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- 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.
- 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.
- Zhenbo Wang & Kameng Nip, 2017. "Bin packing under linear constraints," Journal of Combinatorial Optimization, Springer, vol. 34(4), pages 1198-1209, November.
- Nip, Kameng & Wang, Zhenbo & Wang, Zizhuo, 2016. "Scheduling under linear constraints," European Journal of Operational Research, Elsevier, vol. 253(2), pages 290-297.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Brammer, Janis & Lutz, Bernhard & Neumann, Dirk, 2022. "Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning," European Journal of Operational Research, Elsevier, vol. 299(1), pages 75-86.
- Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.
- Jerzy Kamburowski, 2003. "On the unknown contribution of Stefan Chanas to the stochastic flow shop analysis," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 13(4), pages 75-83.
- 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.
- 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.
- Byung-Cheon Choi & Joseph Y.-T. Leung & Michael L. Pinedo, 2011. "Minimizing makespan in an ordered flow shop with machine-dependent processing times," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 797-818, November.
- 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.
- Gabriel Mauricio Zambrano-Rey & Eliana María González-Neira & Gabriel Fernando Forero-Ortiz & María José Ocampo-Monsalve & Andrea Rivera-Torres, 2024. "Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns," Annals of Operations Research, Springer, vol. 338(1), pages 801-833, July.
- Thierry Garaix & Salim Rostami & Xiaolan Xie, 2020. "Daily outpatient chemotherapy appointment scheduling with random deferrals," Flexible Services and Manufacturing Journal, Springer, vol. 32(1), pages 129-153, March.
More about this item
Keywords
Scheduling; Flow shop; Linear programming; Computational complexity; Approximation algorithm;All these keywords.
Statistics
Access and download statisticsCorrections
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.