IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v54y2016i16p4854-4881.html
   My bibliography  Save this article

Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach

Author

Listed:
  • Guillermo Campos Ciro
  • Frédéric Dugardin
  • Farouk Yalaoui
  • Russell Kelly

Abstract

The continuous evolution of manufacturing environments leads to a more efficient production process that controls an increasing number of parameters. Production resources usually represent an important constraint in a manufacturing activity, specially talking about the management of human resources and their skills. In order to study the impact of this subject, this paper considers an open shop scheduling problem based on a mechanical production workshop to minimise the total flow time including a multi-skill resource constraint. Then, we count with a number of workers that have a versatility to carry out different tasks, and according to their assignment a schedule is generated. In that way, we have formulated the problem as a linear as and a non-linear mathematical model which applies the classic scheduling constraints, adding some different resources constraints related to personnel staff competences and their availability to execute one task. In addition, we introduce a genetic algorithm and an ant colony optimisation (ACO) method to solve large size problems. Finally, the best method (ACO) has been used to solve a real industrial case that is presented at the end.

Suggested Citation

  • Guillermo Campos Ciro & Frédéric Dugardin & Farouk Yalaoui & Russell Kelly, 2016. "Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4854-4881, August.
    • Handle: RePEc:taf:tprsxx:v:54:y:2016:i:16:p:4854-4881
    DOI: 10.1080/00207543.2015.1126371
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2015.1126371
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2015.1126371?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. Bräsel, Heidemarie & Herms, André & Mörig, Marc & Tautenhahn, Thomas & Tusch, Jan & Werner, Frank, 2008. "Heuristic constructive algorithms for open shop scheduling to minimize mean flow time," European Journal of Operational Research, Elsevier, vol. 189(3), pages 856-870, September.
    2. Cai, X. & Li, K. N., 2000. "A genetic algorithm for scheduling staff of mixed skills under multi-criteria," European Journal of Operational Research, Elsevier, vol. 125(2), pages 359-369, September.
    3. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    4. Loukil, T. & Teghem, J. & Tuyttens, D., 2005. "Solving multi-objective production scheduling problems using metaheuristics," European Journal of Operational Research, Elsevier, vol. 161(1), pages 42-61, February.
    5. Wallace J. Hopp & Eylem Tekin & Mark P. Van Oyen, 2004. "Benefits of Skill Chaining in Serial Production Lines with Cross-Trained Workers," Management Science, INFORMS, vol. 50(1), pages 83-98, January.
    6. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    7. Giaro, Krzysztof, 2001. "NP-hardness of compact scheduling in simplified open and flow shops," European Journal of Operational Research, Elsevier, vol. 130(1), pages 90-98, April.
    8. Liaw, Ching-Fang, 2000. "A hybrid genetic algorithm for the open shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 124(1), pages 28-42, July.
    9. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    10. Christian Prins, 2000. "Competitive genetic algorithms for the open-shop scheduling problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 52(3), pages 389-411, December.
    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. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    2. Mejía, Gonzalo & Yuraszeck, Francisco, 2020. "A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times," European Journal of Operational Research, Elsevier, vol. 285(2), pages 484-496.
    3. Yiwei Fan & Gang Wang & Xiaoling Lu & Gaobin Wang, 2019. "Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands," PLOS ONE, Public Library of Science, vol. 14(12), pages 1-26, December.
    4. David Füßler & Stefan Fedtke & Nils Boysen, 2019. "The cafeteria problem: order sequencing and picker routing in on-the-line picking systems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(3), pages 727-756, September.
    5. Tamás Bányai & Christian Landschützer & Ágota Bányai, 2018. "Markov-Chain Simulation-Based Analysis of Human Resource Structure: How Staff Deployment and Staffing Affect Sustainable Human Resource Strategy," Sustainability, MDPI, vol. 10(10), pages 1-21, October.
    6. Li Zhou & Zhaochan Li & Ning Shi & Shaohua Liu & Ke Xiong, 2019. "Performance Analysis of Three Intelligent Algorithms on Route Selection of Fishbone Layout," Sustainability, MDPI, vol. 11(4), pages 1-17, February.

    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. Mejía, Gonzalo & Yuraszeck, Francisco, 2020. "A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times," European Journal of Operational Research, Elsevier, vol. 285(2), pages 484-496.
    2. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    3. Selcuk Colak & Anurag Agarwal, 2005. "Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(7), pages 631-644, October.
    4. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    5. Pempera, Jaroslaw & Smutnicki, Czeslaw, 2018. "Open shop cyclic scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 773-781.
    6. Arnaud Malapert & Hadrien Cambazard & Christelle Guéret & Narendra Jussien & André Langevin & Louis-Martin Rousseau, 2012. "An Optimal Constraint Programming Approach to the Open-Shop Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 228-244, May.
    7. Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.
    8. Ansis Ozolins, 2021. "Dynamic programming approach for solving the open shop 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(1), pages 291-306, March.
    9. Kumar, Akhilesh & Prakash & Tiwari, M.K. & Shankar, Ravi & Baveja, Alok, 2006. "Solving machine-loading problem of a flexible manufacturing system with constraint-based genetic algorithm," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1043-1069, December.
    10. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 0. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    11. Lizhong Zhao & Chen-Fu Chien & Mitsuo Gen, 2018. "A bi-objective genetic algorithm for intelligent rehabilitation scheduling considering therapy precedence constraints," Journal of Intelligent Manufacturing, Springer, vol. 29(5), pages 973-988, June.
    12. Geiger, Martin Josef, 2007. "On operators and search space topology in multi-objective flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 181(1), pages 195-206, August.
    13. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 2020. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 547-569, August.
    14. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    15. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.
    16. Jianhui Mou & Xinyu Li & Liang Gao & Wenchao Yi, 2018. "An effective L-MONG algorithm for solving multi-objective flow-shop inverse scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 29(4), pages 789-807, April.
    17. Ciavotta, Michele & Minella, Gerardo & Ruiz, Rubén, 2013. "Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study," European Journal of Operational Research, Elsevier, vol. 227(2), pages 301-313.
    18. Tamer Abdelmaguid & Mohamed Shalaby & Mohamed Awwad, 2014. "A tabu search approach for proportionate multiprocessor open shop scheduling," Computational Optimization and Applications, Springer, vol. 58(1), pages 187-203, May.
    19. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    20. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.

    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:taf:tprsxx:v:54:y:2016:i:16:p:4854-4881. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.