IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v43y1996i5p721-735.html
   My bibliography  Save this article

A total tardiness problem with preprocessing included

Author

Listed:
  • Christos Koulamas

Abstract

A special case of the two‐machine flow‐shop total tardiness problem is defined by assuming that the first machine is dedicated to preprocessing and that the second machine performs the main operation, which is longer than preprocessing for each job. It is also assumed that customer orders (jobs) contain varying numbers of otherwise similar parts; therefore orders with longer main processing times have longer preprocessing times as well. The new problem (F2/ppc/T) is solved by exploiting its structure and its relationship to the single‐machine (1//T) and the two‐machine flow‐shop (F2//T¯) total tardiness problems. It is shown that shortest‐processing‐time ordering minimizes the average job completion time in the F2/ppc/T setting. This result leads to the development of dominance conditions to determine a priori the order of some jobs in an optimal F2/ppc/T sequence. These dominance conditions are then embedded in a branch‐and‐bound algorithm, which is shown to be computationally efficient. A polynomial‐time heuristic is also developed for F2/ppc/T. It is concluded that the additional structure of F2/ppc/T (compared to the general F2//T problem) results in highly efficient solution algorithms for it. © 1996 John Wiley & Sons, Inc.

Suggested Citation

  • Christos Koulamas, 1996. "A total tardiness problem with preprocessing included," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(5), pages 721-735, August.
    • Handle: RePEc:wly:navres:v:43:y:1996:i:5:p:721-735
    DOI: 10.1002/(SICI)1520-6750(199608)43:53.0.CO;2-7
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199608)43:53.0.CO;2-7
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199608)43:53.0.CO;2-7?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
    ---><---

    References listed on IDEAS

    as
    1. Jianzhong Du & Joseph Y.-T. Leung, 1990. "Minimizing Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 483-495, August.
    2. 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.
    3. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total flow time with unequal release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(6), pages 859-875, October.
    4. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total tardiness with different release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 265-283, March.
    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. Christos Koulamas, 1997. "Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(1), pages 109-125, February.
    2. Philippe Baptiste & Ruslan Sadykov, 2009. "On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(6), pages 487-502, September.
    3. 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.
    4. K. H. Adjallah & K. P. Adzakpa, 2007. "Minimizing maintenance cost involving flow-time and tardiness penalty with unequal release dates," Journal of Risk and Reliability, , vol. 221(1), pages 57-65, March.
    5. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    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. Hongfeng Wang & Min Huang & Junwei Wang, 2019. "An effective metaheuristic algorithm for flowshop scheduling with deteriorating jobs," Journal of Intelligent Manufacturing, Springer, vol. 30(7), pages 2733-2742, October.
    8. Adel Kacem & Abdelaziz Dammak, 2021. "Multi-objective scheduling on two dedicated processors," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 694-721, October.
    9. 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.
    10. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.
    11. Liqi Zhang & Lingfa Lu & Shisheng Li, 2016. "New results on two-machine flow-shop scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1493-1504, May.
    12. Quang Chieu Ta & Jean-Charles Billaut & Jean-Louis Bouquard, 2018. "Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 617-628, March.
    13. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    14. Golpîra, Hêriş, 2020. "Smart Energy-Aware Manufacturing Plant Scheduling under Uncertainty: A Risk-Based Multi-Objective Robust Optimization Approach," Energy, Elsevier, vol. 209(C).
    15. Alexander Grigoriev & Martijn Holthuijsen & Joris van de Klundert, 2005. "Basic scheduling problems with raw material constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 527-535, September.
    16. Fernández, Elena & Munoz-Marquez, Manuel, 2022. "New formulations and solutions for the strategic berth template problem," European Journal of Operational Research, Elsevier, vol. 298(1), pages 99-117.
    17. Yadong Wang & Baoqiang Fan & Jingang Zhai & Wei Xiong, 2019. "Two-machine flowshop scheduling in a physical examination center," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 363-374, January.
    18. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    19. 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.
    20. Peng-Yeng Yin & Hsin-Min Chen & Yi-Lung Cheng & Ying-Chieh Wei & Ya-Lin Huang & Rong-Fuh Day, 2021. "Minimizing the Makespan in Flowshop Scheduling for Sustainable Rubber Circular Manufacturing," Sustainability, MDPI, vol. 13(5), pages 1-18, February.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:43:y:1996:i:5:p:721-735. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.