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

Multiproduct batching and scheduling with buffered rework: The case of a car paint shop

Author

Listed:
  • Florian Jaehn
  • Sergey Kovalev
  • Mikhail Y. Kovalyov
  • Erwin Pesch

Abstract

We study a problem of scheduling products on the same facility, which is motivated by a car paint shop. Items of the same product are identical. Operations on the items are performed sequentially in batches, where each batch is a set of operations on the same product. Some of the produced items are of the required good quality and some items can be defective. Defectiveness of an item is determined by a given simulated function of its product, its preceding product, and the position of its operation in the batch. Defective items are kept in a buffer of a limited capacity, and they are then remanufactured at the same facility. A minimum waiting time exists for any defective item before its remanufacturing can commence. Each product has a sequence independent setup time which precedes its first operation or its operation following an operation of another product. A due date is given for each product such that all items of the same product have the same due date and the objective is to find a schedule which minimizes maximum lateness of product completion times with respect to their due dates. The problem is proved NP‐hard in the strong sense, and a heuristic Group Technology (GT) solution approach is suggested and analyzed. The results justify application of the GT approach to scheduling real car paint shops with buffered rework. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 458–471, 2014

Suggested Citation

  • Florian Jaehn & Sergey Kovalev & Mikhail Y. Kovalyov & Erwin Pesch, 2014. "Multiproduct batching and scheduling with buffered rework: The case of a car paint shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(6), pages 458-471, September.
  • Handle: RePEc:wly:navres:v:61:y:2014:i:6:p:458-471
    DOI: 10.1002/nav.21596
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21596
    Download Restriction: no

    References listed on IDEAS

    as
    1. Giard, Vincent & Jeunet, Jully, 2010. "Optimal sequencing of mixed models with sequence-dependent setups and utility workers on an assembly line," International Journal of Production Economics, Elsevier, vol. 123(2), pages 290-300, February.
    2. Tadeusz J. Sawik, 1993. "A scheduling algorithm for flexible flow lines with limited intermediate buffers," Applied Stochastic Models and Data Analysis, John Wiley & Sons, vol. 9(2), pages 127-138, June.
    3. Solnon, Christine & Cung, Van Dat & Nguyen, Alain & Artigues, Christian, 2008. "The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF'2005 challenge problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 912-927, December.
    4. Golle, Uli & Boysen, Nils & Rothlauf, Franz, 2010. "Analysis and design of sequencing rules for car sequencing," European Journal of Operational Research, Elsevier, vol. 206(3), pages 579-585, November.
    5. Gyorgy Dosa & Zhiyi Tan & Zsolt Tuza & Yujie Yan & Cecília Sik Lányi, 2014. "Improved bounds for batch scheduling with nonidentical job sizes," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 351-358, August.
    6. 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.
    7. Inderfurth, Karl & Kovalyov, Mikhail Y. & Ng, C.T. & Werner, Frank, 2007. "Cost minimizing scheduling of work and rework processes on a single facility under deterioration of reworkables," International Journal of Production Economics, Elsevier, vol. 105(2), pages 345-356, February.
    8. repec:dau:papers:123456789/2861 is not listed on IDEAS
    9. Lixin Tang & Hua Gong & Jiyin Liu & Feng Li, 2014. "Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(4), pages 269-285, June.
    10. Liaee, Mohammad Mehdi & Emmons, Hamilton, 1997. "Scheduling families of jobs with setup times," International Journal of Production Economics, Elsevier, vol. 51(3), pages 165-176, September.
    11. Liu, John J. & Yang, Ping, 1996. "Optimal lot-sizing in an imperfect production system with homogeneous reworkable jobs," European Journal of Operational Research, Elsevier, vol. 91(3), pages 517-527, June.
    12. Wee, Hui Ming & Widyadana, Gede Agus, 2013. "A production model for deteriorating items with stochastic preventive maintenance time and rework process with FIFO rule," Omega, Elsevier, vol. 41(6), pages 941-954.
    13. Cordeau, Jean-François & Laporte, Gilbert & Pasin, Federico, 2008. "Iterated tabu search for the car sequencing problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 945-956, December.
    14. 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.
    15. Meyr, H., 2004. "Supply chain planning in the German automotive industry," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 36062, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    16. Gagne, Caroline & Gravel, Marc & Price, Wilson L., 2006. "Solving real car sequencing problems with ant colony optimization," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1427-1448, 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. Gribkovskaia, Irina V. & Kovalev, Sergey & Werner, Frank, 2010. "Batching for work and rework processes on dedicated facilities to minimize the makespan," Omega, Elsevier, vol. 38(6), pages 522-527, December.
    2. A. Dolgui & M. Kovalyov & K. Shchamialiova, 2011. "Multi-product lot-sizing and sequencing on a single imperfect machine," Computational Optimization and Applications, Springer, vol. 50(3), pages 465-482, December.
    3. Golle, Uli & Rothlauf, Franz & Boysen, Nils, 2014. "Car sequencing versus mixed-model sequencing: A computational study," European Journal of Operational Research, Elsevier, vol. 237(1), pages 50-61.
    4. Grundel, Soesja & Çiftçi, Barış & Borm, Peter & Hamers, Herbert, 2013. "Family sequencing and cooperation," European Journal of Operational Research, Elsevier, vol. 226(3), pages 414-424.
    5. Parames Chutima & Sathaporn Olarnviwatchai, 0. "A multi-objective car sequencing problem on two-sided assembly lines," Journal of Intelligent Manufacturing, Springer, vol. 0, pages 1-20.
    6. Boysen, Nils & Scholl, Armin & Wopperer, Nico, 2012. "Resequencing of mixed-model assembly lines: Survey and research agenda," European Journal of Operational Research, Elsevier, vol. 216(3), pages 594-604.
    7. Staeblein, Thomas & Aoki, Katsuki, 2015. "Planning and scheduling in the automotive industry: A comparison of industrial practice at German and Japanese makers," International Journal of Production Economics, Elsevier, vol. 162(C), pages 258-272.
    8. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Nossack, Jenny & Pesch, Erwin, 2014. "Minimizing setup costs in a transfer line design problem with sequential operation processing," International Journal of Production Economics, Elsevier, vol. 151(C), pages 186-194.
    9. Buergin, Jens & Hammerschmidt, Andreas & Hao, Han & Kramer, Sergej & Tutsch, Hansjoerg & Lanza, Gisela, 2019. "Robust order planning with planned orders for multi-variant series production in a production network," International Journal of Production Economics, Elsevier, vol. 210(C), pages 107-119.
    10. Parames Chutima & Sathaporn Olarnviwatchai, 2018. "A multi-objective car sequencing problem on two-sided assembly lines," Journal of Intelligent Manufacturing, Springer, vol. 29(7), pages 1617-1636, October.
    11. Karim Aroui & Gülgün Alpan & Yannick Frein, 2017. "Minimising work overload in mixed-model assembly lines with different types of operators: a case study from the truck industry," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6305-6326, November.
    12. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    13. Hinder, Oliver & Mason, Andrew J., 2017. "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness," European Journal of Operational Research, Elsevier, vol. 262(2), pages 411-423.
    14. Waldherr, Stefan & Knust, Sigrid, 2017. "Decomposition algorithms for synchronous flow shop problems with additional resources and setup times," European Journal of Operational Research, Elsevier, vol. 259(3), pages 847-863.
    15. Kramer, Arthur & Iori, Manuel & Lacomme, Philippe, 2021. "Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization," European Journal of Operational Research, Elsevier, vol. 289(3), pages 825-840.
    16. Li, Shisheng & Ng, C.T. & Yuan, Jinjiang, 2011. "Group scheduling and due date assignment on a single machine," International Journal of Production Economics, Elsevier, vol. 130(2), pages 230-235, April.
    17. Barketau, M.S. & Cheng, T.C.E. & Kovalyov, M.Y., 2008. "Batch scheduling of deteriorating reworkables," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1317-1326, September.
    18. Sonntag, Danja & Kiesmüller, Gudrun P., 2018. "Disposal versus rework – Inventory control in a production system with random yield," European Journal of Operational Research, Elsevier, vol. 267(1), pages 138-149.
    19. Ji, Min & Cheng, T.C.E., 2010. "Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan," European Journal of Operational Research, Elsevier, vol. 202(1), pages 90-98, April.
    20. repec:spr:compst:v:68:y:2008:i:2:p:277-293 is not listed on IDEAS
    21. Janiak, Adam & Kovalyov, Mikhail Y. & Portmann, Marie-Claude, 2005. "Single machine group scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 162(1), pages 112-121, April.

    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:61:y:2014:i:6:p:458-471. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wiley Content Delivery). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.