IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v217y2014i1p263-27910.1007-s10479-014-1531-8.html
   My bibliography  Save this article

Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence

Author

Listed:
  • F. Hwang
  • M. Kovalyov
  • B. Lin

Abstract

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n 7 ) time. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • F. Hwang & M. Kovalyov & B. Lin, 2014. "Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence," Annals of Operations Research, Springer, vol. 217(1), pages 263-279, June.
    • Handle: RePEc:spr:annopr:v:217:y:2014:i:1:p:263-279:10.1007/s10479-014-1531-8
    DOI: 10.1007/s10479-014-1531-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-014-1531-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-014-1531-8?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. F J Hwang & B M T Lin, 2012. "Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(6), pages 839-845, June.
    2. Kovalyov, M. Y. & Potts, C. N. & Strusevich, V. A., 2004. "Batching decisions for assembly production systems," European Journal of Operational Research, Elsevier, vol. 157(3), pages 620-642, September.
    3. Sourd, Francis, 2005. "Optimal timing of a sequence of tasks with general completion costs," European Journal of Operational Research, Elsevier, vol. 165(1), pages 82-96, August.
    4. A.E. Gerodimos & C.A. Glass & C.N. Potts & T. Tautenhahn, 1999. "Scheduling multi‐operation jobs on a single machine," Annals of Operations Research, Springer, vol. 92(0), pages 87-105, January.
    5. Gerodimos, Alex E. & Glass, Celia A. & Potts, Chris N., 2000. "Scheduling the production of two-component jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 120(2), pages 250-259, January.
    6. 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.
    7. 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.
    8. John J. Kanet & V. Sridharan, 2000. "Scheduling with Inserted Idle Time: Problem Taxonomy and Literature Review," Operations Research, INFORMS, vol. 48(1), pages 99-110, February.
    9. Y.M. Shafransky & V.A. Strusevich, 1998. "The open shop scheduling problem with a given sequence of jobs on one machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 705-731, October.
    10. B. Lin & T. Cheng, 2005. "Two-Machine Flowshop Batching and Scheduling," Annals of Operations Research, Springer, vol. 133(1), pages 149-161, January.
    11. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    12. T.C.E. Cheng & B.M.T. Lin & A. Toker, 2000. "Makespan minimization in the two‐machine flowshop batch scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(2), pages 128-144, March.
    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. T.C.E. Cheng & Svetlana A. Kravchenko & Bertrand M. T. Lin, 2019. "Server scheduling on parallel dedicated machines with fixed job sequences," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 321-332, June.
    2. Bertrand M. T. Lin & F. J. Hwang & Jatinder N. D. Gupta, 2017. "Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence," Journal of Scheduling, Springer, vol. 20(3), pages 293-302, June.

    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. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    2. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    3. Zhou, Feng & Blocher, James D. & Hu, Xinxin & Sebastian Heese, H., 2014. "Optimal single machine scheduling of products with components and changeover cost," European Journal of Operational Research, Elsevier, vol. 233(1), pages 75-83.
    4. B. M. T. Lin & T. C. E. Cheng, 2011. "Scheduling with centralized and decentralized batching policies in concurrent open shops," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(1), pages 17-27, February.
    5. Xinxin Hu & James D Blocher & Hans Sebastian Heese & Feng Zhou, 2016. "Scheduling products with subassemblies and changeover time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(8), pages 1025-1033, August.
    6. 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.
    7. A. G. Leeftink & R. J. Boucherie & E. W. Hans & M. A. M. Verdaasdonk & I. M. H. Vliegen & P. J. Diest, 2018. "Batch scheduling in the histopathology laboratory," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 171-197, June.
    8. B. Lin & T. Cheng, 2005. "Two-Machine Flowshop Batching and Scheduling," Annals of Operations Research, Springer, vol. 133(1), pages 149-161, January.
    9. S.S. Panwalkar & Christos Koulamas, 2015. "Scheduling research and the first decade of NRLQ: A historical perspective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 335-344, June.
    10. T.C.E. Cheng & Svetlana A. Kravchenko & Bertrand M. T. Lin, 2019. "Server scheduling on parallel dedicated machines with fixed job sequences," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 321-332, June.
    11. Zhang, Hongbin & Yang, Yu & Wu, Feng, 2024. "Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine," Omega, Elsevier, vol. 122(C).
    12. A.A. Gladky & Y.M. Shafransky & V.A. Strusevich, 2004. "Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 13-28, March.
    13. Jae-Min Yu & Rong Huang & Dong-Ho Lee, 2017. "Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops," International Journal of Production Research, Taylor & Francis Journals, vol. 55(11), pages 3266-3282, June.
    14. Lin, B.M.T. & Cheng, T.C.E. & Chou, A.S.C., 2007. "Scheduling in an assembly-type production chain with batch transfer," Omega, Elsevier, vol. 35(2), pages 143-151, April.
    15. Fernandez-Viagas, Victor & Talens, Carla & Framinan, Jose M., 2022. "Assembly flowshop scheduling problem: Speed-up procedure and computational evaluation," European Journal of Operational Research, Elsevier, vol. 299(3), pages 869-882.
    16. 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.
    17. 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.
    18. Yijie Li, 2023. "Bicriteria fabrication scheduling of two-component jobs on a single machine," Operational Research, Springer, vol. 23(4), pages 1-13, December.
    19. Dominik Kress & Maksim Barketau & Erwin Pesch, 2018. "Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines," Journal of Scheduling, Springer, vol. 21(6), pages 595-606, December.
    20. Gmys, Jan & Mezmaz, Mohand & Melab, Nouredine & Tuyttens, Daniel, 2020. "A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 814-833.

    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:annopr:v:217:y:2014:i:1:p:263-279:10.1007/s10479-014-1531-8. 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.