IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v29y2021i3d10.1007_s10100-020-00689-3.html
   My bibliography  Save this article

A new heuristic and an exact approach for a production planning problem

Author

Listed:
  • Peter Auer

    (Montanuniversität Leoben)

  • György Dósa

    (University of Pannonia)

  • Tibor Dulai

    (University of Pannonia)

  • Armin Fügenschuh

    (Brandenburgische Technische Universität Cottbus-Senftenberg)

  • Peggy Näser

    (Brandenburgische Technische Universität Cottbus-Senftenberg)

  • Ronald Ortner

    (Montanuniversität Leoben)

  • Ágnes Werner-Stark

    (University of Pannonia)

Abstract

We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The complexity of the problem arises from having a huge number of products from both types. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. We consider a special case, where there are two job types on four different tasks, and four types of machines. Some of the machines are multi-purpose and some operations can be processed by different machine types. The processing time of an operation may depend also on the machine that processes it. The problem is very difficult to solve even in this special setting. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct influence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time.

Suggested Citation

  • Peter Auer & György Dósa & Tibor Dulai & Armin Fügenschuh & Peggy Näser & Ronald Ortner & Ágnes Werner-Stark, 2021. "A new heuristic and an exact approach for a production planning problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(3), pages 1079-1113, September.
  • Handle: RePEc:spr:cejnor:v:29:y:2021:i:3:d:10.1007_s10100-020-00689-3
    DOI: 10.1007/s10100-020-00689-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10100-020-00689-3
    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/s10100-020-00689-3?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. José R. Correa & Andreas S. Schulz, 2005. "Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 1005-1021, November.
    2. Almeder, Christian & Klabjan, Diego & Traxler, Renate & Almada-Lobo, Bernardo, 2015. "Lead time considerations for the multi-level capacitated lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 727-738.
    3. Christodoulos Floudas & Xiaoxia Lin, 2005. "Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications," Annals of Operations Research, Springer, vol. 139(1), pages 131-162, October.
    4. Herrmann, Jeffrey & Proth, Jean-Marie & Sauer, Nathalie, 1997. "Heuristics for unrelated machine scheduling with precedence constraints," European Journal of Operational Research, Elsevier, vol. 102(3), pages 528-537, 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. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    2. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    3. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    4. Agnetis, Alessandro & Kellerer, Hans & Nicosia, Gaia & Pacifici, Andrea, 2012. "Parallel dedicated machines scheduling with chain precedence constraints," European Journal of Operational Research, Elsevier, vol. 221(2), pages 296-305.
    5. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    6. Yanina Fumero & Gabriela Corsano & Jorge Montagna, 2012. "Planning and scheduling of multistage multiproduct batch plants operating under production campaigns," Annals of Operations Research, Springer, vol. 199(1), pages 249-268, October.
    7. Daniel D. Zeng & J. Leon Zhao, 2005. "Effective Role Resolution in Workflow Management," INFORMS Journal on Computing, INFORMS, vol. 17(3), pages 374-387, August.
    8. Farahmand, H. & Doorman, G.L., 2012. "Balancing market integration in the Northern European continent," Applied Energy, Elsevier, vol. 96(C), pages 316-326.
    9. Stefansson, Hlynur & Sigmarsdottir, Sigrun & Jensson, Pall & Shah, Nilay, 2011. "Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry," European Journal of Operational Research, Elsevier, vol. 215(2), pages 383-392, December.
    10. Moo-Sung Sohn & Jiwoong Choi & Hoseog Kang & In-Chan Choi, 2017. "Multiobjective Production Planning at LG Display," Interfaces, INFORMS, vol. 47(4), pages 279-291, August.
    11. Gansterer, Margaretha & Födermayr, Patrick & Hartl, Richard F., 2021. "The capacitated multi-level lot-sizing problem with distributed agents," International Journal of Production Economics, Elsevier, vol. 235(C).
    12. Mancuso, A. & Compare, M. & Salo, A. & Zio, E., 2021. "Optimal Prognostics and Health Management-driven inspection and maintenance strategies for industrial systems," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    13. Yiyong Xiao & Meng You & Xiaorong Zuo & Shenghan Zhou & Xing Pan, 2018. "The Uncapacitatied Dynamic Single-Level Lot-Sizing Problem under a Time-Varying Environment and an Exact Solution Approach," Sustainability, MDPI, vol. 10(11), pages 1-14, October.
    14. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    15. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    16. Dujardin, Yann & Vanderpooten, Daniel & Boillot, Florence, 2015. "A multi-objective interactive system for adaptive traffic control," European Journal of Operational Research, Elsevier, vol. 244(2), pages 601-610.
    17. Grzegorz Bocewicz & Zbigniew Banaszak & Izabela Nielsen, 2019. "Multimodal processes prototyping subject to grid-like network and fuzzy operation time constraints," Annals of Operations Research, Springer, vol. 273(1), pages 561-585, February.
    18. Rohaninejad, Mohammad & Hanzálek, Zdeněk, 2023. "Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches," International Journal of Production Economics, Elsevier, vol. 263(C).
    19. Mohammad Heydari & Yanan Fan & Kin Keung Lai, 2023. "A Robust Site Selection Model under uncertainty for Special Hospital Wards in Hong Kong," Papers 2307.11508, arXiv.org.
    20. Alix Vargas & Carmen Fuster & David Corne, 2020. "Towards Sustainable Collaborative Logistics Using Specialist Planning Algorithms and a Gain-Sharing Business Model: A UK Case Study," Sustainability, MDPI, vol. 12(16), pages 1-29, August.

    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:cejnor:v:29:y:2021:i:3:d:10.1007_s10100-020-00689-3. 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.