IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v23y2020i1d10.1007_s10951-019-00618-6.html
   My bibliography  Save this article

Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines

Author

Listed:
  • S. S. Panwalkar

    (Johns Hopkins University)

  • Christos Koulamas

    (Florida International University)

Abstract

We show by induction that the shortest processing time sequence is optimal for a number of three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines, effectively proving the optimality of an index priority rule when the adjacent job pairwise interchange argument does not hold. We also show that when the middle machine is maximal, the synchronous flow, blocking and no-wait problems are equivalent, because they can be effectively decomposed into two equivalent two-stage problems. A similar equivalence is shown for the classical flow shop and the flow shop with no-idle machines. These equivalences facilitate the solution of one problem by using the optimal algorithm for the equivalent problem. Finally, we observe that when the middle machine is minimal, the optimal sequence is not a pyramid sequence for the synchronous flow and blocking flow shops. On the other hand, we show that the optimal sequence for the flow shop with no-idle machines is a pyramid sequence obtainable by dynamic programming in pseudo-polynomial time.

Suggested Citation

  • S. S. Panwalkar & Christos Koulamas, 2020. "Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines," Journal of Scheduling, Springer, vol. 23(1), pages 145-154, February.
    • Handle: RePEc:spr:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00618-6
    DOI: 10.1007/s10951-019-00618-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-019-00618-6
    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-019-00618-6?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, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    2. Kalczynski, Pawel Jan & Kamburowski, Jerzy, 2007. "On no-wait and no-idle flow shops with makespan criterion," European Journal of Operational Research, Elsevier, vol. 178(3), pages 677-685, May.
    3. 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.
    4. Waldherr, Stefan & Knust, Sigrid, 2015. "Complexity results for flow shop problems with synchronous movement," European Journal of Operational Research, Elsevier, vol. 242(1), pages 34-44.
    5. S.S. Panwalkar & Milton L. Smith & Christos Koulamas, 2013. "Review of the ordered and proportionate flow shop scheduling research," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 46-55, February.
    6. Jian-Ya Ding & Shiji Song & Jatinder N.D. Gupta & Cheng Wang & Rui Zhang & Cheng Wu, 2016. "New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4759-4772, August.
    7. 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.
    8. I. Adiri & D. Pohoryles, 1982. "Flowshop/no‐idle or no‐wait scheduling to minimize the sum of completion times," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 29(3), pages 495-504, September.
    9. Goncharov, Yaroslav & Sevastyanov, Sergey, 2009. "The flow shop problem with no-idle constraints: A review and approximation," European Journal of Operational Research, Elsevier, vol. 196(2), pages 450-456, July.
    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. 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.
    2. 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.
    3. 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.
    4. Koulamas, Christos & Kyparisis, George J., 2023. "Two-stage no-wait proportionate flow shop scheduling with minimal service time variation and optional job rejection," European Journal of Operational Research, Elsevier, vol. 305(2), pages 608-616.
    5. 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.
    6. 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.
    7. 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.
    8. Wenjie Li & Jinjiang Yuan, 2021. "Single-machine online scheduling of jobs with non-delayed processing constraint," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 830-843, May.
    9. Tolga Bektaş & Alper Hamzadayı & Rubén Ruiz, 2020. "Benders decomposition for the mixed no-idle permutation flowshop scheduling problem," Journal of Scheduling, Springer, vol. 23(4), pages 513-523, August.
    10. Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    11. Allahverdi, Ali & Aydilek, Harun & Aydilek, Asiye, 2018. "No-wait flowshop scheduling problem with two criteria; total tardiness and makespan," European Journal of Operational Research, Elsevier, vol. 269(2), pages 590-601.
    12. Polten, Lukas & Emde, Simon, 2021. "Scheduling automated guided vehicles in very narrow aisle warehouses," Omega, Elsevier, vol. 99(C).
    13. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    14. Ivan Kristianto Singgih & Onyu Yu & Byung-In Kim & Jeongin Koo & Seungdoe Lee, 2020. "Production scheduling problem in a factory of automobile component primer painting," Journal of Intelligent Manufacturing, Springer, vol. 31(6), pages 1483-1496, August.
    15. Xuemei Qi & Hongtao Wang & Haihong Zhu & Ji Zhang & Fulong Chen & Jie Yang, 2016. "Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4957-4972, August.
    16. Guo-Sheng Liu & Jin-Jin Li & Ying-Si Tang, 2018. "Minimizing Total Idle Energy Consumption in the Permutation Flow Shop Scheduling Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(06), pages 1-19, December.
    17. Stefansdottir, Bryndis & Grunow, Martin & Akkerman, Renzo, 2017. "Classifying and modeling setups and cleanings in lot sizing and scheduling," European Journal of Operational Research, Elsevier, vol. 261(3), pages 849-865.
    18. Groflin, Heinz & Klinkert, Andreas, 2007. "Feasible insertions in job shop scheduling, short cycles and stable sets," European Journal of Operational Research, Elsevier, vol. 177(2), pages 763-785, March.
    19. Neil Geismar, H. & Dawande, Milind & Sriskandarajah, Chelliah, 2005. "Approximation algorithms for k-unit cyclic solutions in robotic cells," European Journal of Operational Research, Elsevier, vol. 162(2), pages 291-309, April.
    20. Jin Qian & Haiyan Han, 2022. "Improved algorithms for proportionate flow shop scheduling with due-window assignment," Annals of Operations Research, Springer, vol. 309(1), pages 249-258, February.

    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:23:y:2020:i:1:d:10.1007_s10951-019-00618-6. 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.