IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v288y2021i1p14-29.html
   My bibliography  Save this article

A meta-heuristic to solve the just-in-time job-shop scheduling problem

Author

Listed:
  • Ahmadian, Mohammad Mahdi
  • Salehipour, Amir
  • Cheng, T.C.E.

Abstract

Just-in-time job-shop scheduling (JIT-JSS) is a variant of the job-shop scheduling problem, in which each operation has a distinct due-date and any deviation of the operation completion time from its due-date incurs an earliness or tardiness penalty. We develop a variable neighbourhood search (VNS) algorithm to solve JIT-JSS. The algorithm operates by decomposing JIT-JSS into smaller problems, obtaining optimal or near-optimal sequences of performing the operations for those smaller problems, and generating a schedule, i.e., determining the completion time of the operations, for JIT-JSS. The algorithm uses several neighbourhood structures, including the new relaxation neighbourhoods developed in this study, to obtain a quality sequence. The relaxation neighbourhoods partially destruct (relax) the sequence and then re-construct (sequence) certain operations. Differing from the classical neighbourhoods, in which manipulations are performed either randomly or myopically, the moves in the new neighbourhoods are made with reference to other operations, so their impacts on the whole sequence are well considered. By solving a set of 72 benchmark instances, ranging from 10 to 20 jobs and 20 to 200 operations, and comparing the outcomes of the proposed algorithm with the state-of-the-art solution methods in the literature, we obtain new best solutions for nearly 57% of the instances, including new best solutions for 80% of the instances with 20 jobs. The computational results demonstrate the efficacy of the proposed VNS algorithm.

Suggested Citation

  • Ahmadian, Mohammad Mahdi & Salehipour, Amir & Cheng, T.C.E., 2021. "A meta-heuristic to solve the just-in-time job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 288(1), pages 14-29.
    • Handle: RePEc:eee:ejores:v:288:y:2021:i:1:p:14-29
    DOI: 10.1016/j.ejor.2020.04.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720303519
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.04.017?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. Zhou, Hong & Cheung, Waiman & Leung, Lawrence C., 2009. "Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm," European Journal of Operational Research, Elsevier, vol. 194(3), pages 637-649, May.
    2. Boysen, Nils & Emde, Simon & Hoeck, Michael & Kauderer, Markus, 2015. "Part logistics in the automotive industry: Decision problems, literature review and research agenda," European Journal of Operational Research, Elsevier, vol. 242(1), pages 107-120.
    3. Pham, Dinh-Nguyen & Klinkert, Andreas, 2008. "Surgical case scheduling as a generalized job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1011-1025, March.
    4. Bennell, Julia A. & Mesgarpour, Mohammad & Potts, Chris N., 2017. "Dynamic scheduling of aircraft landings," European Journal of Operational Research, Elsevier, vol. 258(1), pages 315-327.
    5. Yvan Dumas & François Soumis & Jacques Desrosiers, 1990. "Technical Note—Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience Costs," Transportation Science, INFORMS, vol. 24(2), pages 145-152, May.
    6. Mohammed Al-Salem & Leonardo Bedoya-Valencia & Ghaith Rabadi, 2016. "Heuristic and Exact Algorithms for the Two-Machine Just in Time Job Shop Scheduling Problem," Mathematical Problems in Engineering, Hindawi, vol. 2016, pages 1-11, November.
    7. Sunxin Wang & Yan Li, 2014. "Variable Neighbourhood Search and Mathematical Programming for Just-in-Time Job-Shop Scheduling Problem," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-9, April.
    8. Boysen, Nils & Emde, Simon & Hoeck, Michael & Kauderer, Markus, 2015. "Part logistics in the automotive industry: Decision problems, literature review and research agenda," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79443, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Wan, Guohua & Yen, Benjamin P.-C., 2009. "Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 195(1), pages 89-97, May.
    10. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    11. Flamini, Marta & Pacciarelli, Dario, 2008. "Real time management of a metro rail terminus," European Journal of Operational Research, Elsevier, vol. 189(3), pages 746-761, September.
    12. 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.
    13. Braune, R. & Zäpfel, G. & Affenzeller, M., 2012. "An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective," European Journal of Operational Research, Elsevier, vol. 218(1), pages 76-85.
    14. J. Beck & Philippe Refalo, 2003. "A Hybrid Approach to Scheduling with Earliness and Tardiness Costs," Annals of Operations Research, Springer, vol. 118(1), pages 49-71, February.
    15. Ramesh Bollapragada & Norman M. Sadeh, 2004. "Proactive release procedures for just‐in‐time job shop environments, subject to machine failures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(7), pages 1018-1044, October.
    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. Shahed Mahmud & Ripon K. Chakrabortty & Alireza Abbasi & Michael J. Ryan, 2022. "Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 33(7), pages 1939-1966, October.
    2. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    3. Ying Sun & Jeng-Shyang Pan & Pei Hu & Shu-Chuan Chu, 2023. "Enhanced Equilibrium Optimizer algorithm applied in job shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 34(4), pages 1639-1665, April.

    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. Mohammad Mahdi Ahmadian & Amir Salehipour, 2021. "The just-in-time job-shop scheduling problem with distinct due-dates for operations," Journal of Heuristics, Springer, vol. 27(1), pages 175-204, April.
    2. Timo Gschwind & Stefan Irnich & Simon Emde & Christian Tilk, 2018. "Branch-Cut-and-Price for the Scheduling Deliveries with Time Windows in a Direct Shipping Network," Working Papers 1805, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    3. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    4. Meyer, Anne & Amberg, Boris, 2018. "Transport concept selection considering supplier milk runs – An integrated model and a case study from the automotive industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 147-169.
    5. Simon Emde, 2017. "Scheduling the replenishment of just-in-time supermarkets in assembly plants," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 321-345, January.
    6. Masood Fathi & Victoria Rodríguez & Dalila B.M.M. Fontes & Maria Jesus Alvarez, 2016. "A modified particle swarm optimisation algorithm to solve the part feeding problem at assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 878-893, February.
    7. Jun Wang & Jingbo Yin & Rafi Ullah Khan & Siqi Wang & Tie Zheng, 2021. "A Study of Inbound Logistics Mode Based on JIT Production in Cruise Ship Construction," Sustainability, MDPI, vol. 13(3), pages 1-18, February.
    8. Timo Gschwind & Stefan Irnich & Christian Tilk & Simon Emde, 2020. "Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network," Journal of Scheduling, Springer, vol. 23(3), pages 363-377, June.
    9. Mustapha Sali & Evren Sahin, 2016. "Line feeding optimization for Just in Time assembly lines: an application to the automotive industry," Post-Print hal-01265041, HAL.
    10. Wenquan Dong & Mingzhou Jin & Yanyan Wang & Peter Kelle, 2021. "Retrieval scheduling in crane-based 3D automated retrieval and storage systems with shuttles," Annals of Operations Research, Springer, vol. 302(1), pages 111-135, July.
    11. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2020. "Loading tow trains ergonomically for just-in-time part supply," European Journal of Operational Research, Elsevier, vol. 284(1), pages 325-344.
    12. Dulebenets, Maxim A., 2019. "A Delayed Start Parallel Evolutionary Algorithm for just-in-time truck scheduling at a cross-docking facility," International Journal of Production Economics, Elsevier, vol. 212(C), pages 236-258.
    13. Quetschlich, Mathias & Moetz, André & Otto, Boris, 2021. "Optimisation model for multi-item multi-echelon supply chains with nested multi-level products," European Journal of Operational Research, Elsevier, vol. 290(1), pages 144-158.
    14. Sali, Mustapha & Sahin, Evren, 2016. "Line feeding optimization for Just in Time assembly lines: An application to the automotive industry," International Journal of Production Economics, Elsevier, vol. 174(C), pages 54-67.
    15. Emde, Simon & Gendreau, Michel, 2017. "Scheduling in-house transport vehicles to feed parts to automotive assembly lines," European Journal of Operational Research, Elsevier, vol. 260(1), pages 255-267.
    16. Lijun Liu & Zhixin Long & Chuangchuang Kou & Haozeng Guo & Xinyu Li, 2023. "Evaluation of the Environmental Cost of Integrated Inbound Logistics: A Case Study of a Gigafactory of a Chinese Logistics Firm," Sustainability, MDPI, vol. 15(15), pages 1-20, July.
    17. Rui Xu & Yumiao Huang & Wei Xiao, 2023. "A Two-Level Variable Neighborhood Descent for a Split Delivery Clustered Vehicle Routing Problem with Soft Cluster Conflicts and Customer-Related Costs," Sustainability, MDPI, vol. 15(9), pages 1-22, May.
    18. Young-Kyou Ha & Su-Han Woo, 2022. "Transportation Infrastructure or Economic Power? Development of the Automobile Industry in the United States," Sustainability, MDPI, vol. 14(3), pages 1-11, January.
    19. Morett, Emilio & Tappia, Elena & Melacini, Marco, 2021. "Scheduling mobile robots in part feeding systems," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Kersten, Wolfgang & Ringle, Christian M. & Blecker, Thorsten (ed.), Adapting to the Future: How Digitalization Shapes Sustainable Logistics and Resilient Supply Chain Management. Proceedings of the Hamburg Internationa, volume 31, pages 129-149, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    20. Glock, Christoph H. & Grosse, Eric H. & Abedinnia, Hamid & Emde, Simon, 2019. "An integrated model to improve ergonomic and economic performance in order picking by rotating pallets," European Journal of Operational Research, Elsevier, vol. 273(2), pages 516-534.

    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:eee:ejores:v:288:y:2021:i:1:p:14-29. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.