Addressing a Complex Manufacturing Problem using Linear Programming Modelization and MOSA Metaheuristic

Authors

  • SEKKAL Norelhouda  Tlemcen Higher School of Applied Sciences/ BP 165 RP, Bel Horizon, Tlemcen 13000, Algeria
  • SEKKAL Djazia Nadjat  Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen 13000, Algeria
  • EL OUCHDI Mouna  Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen 13000, Algeria
  • BELKAID Faycal  Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen 13000, Algeria

Keywords:

Metaheuristic, Linear Programing, Resources Cost, Unrelated Parallel Machine.

Abstract

In this paper, we delve into the unrelated parallel machines static scheduling problem, considering both renewable and non-renewable resource conditions, and accounting for the deterioration effect. The primary challenge lies in determining the optimal assignment of tasks to machines and the efficient allocation of resources, aiming to minimize both the makespan and the cost of non-renewable resources. To address these goals, we develop a mathematical programming model and apply a multi-objective simulated annealing algorithm to our problem. Our computational experiments encompass a range of instances, including small, medium, and large scenarios. The mathematical model proves effective for small instances with 8N2M, 10N3M, and 15N3M, providing solutions to the problem. Remarkably, for these instances, the MOSA approach achieves optimal solutions similar to those obtained by the solver but does so within a shorter computational timeframe.

References

  1. Pfund, J. W. Fowler, et J. N. D. Gupta, « A SURVEY OF ALGORITHMS FOR SINGLE AND MULTI-OBJECTIVE UNRELATED PARALLEL-MACHINE DETERMINISTIC SCHEDULING PROBLEMS », J. Chin. Inst. Ind. Eng., vol. 21, no 3, p. 230­241, janv. 2004, doi: 10.1080/10170660409509404.
  2. Browne et U. Yechiali, « Scheduling Deteriorating Jobs on a Single Processor », Oper. Res., vol. 38, no 3, p. 495­498, juin 1990, doi: 10.1287/opre.38.3.495.
  3. L. Daniels, B. J. Hoopes, et J. B. Mazzola, « Scheduling Parallel Manufacturing Cells with Resource Flexibility », Manag. Sci., vol. 42, no 9, p. 1260­1276, sept. 1996, doi: 10.1287/mnsc.42.9.1260.
  4. Fanjul-Peyro, F. Perea, et R. Ruiz, « Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources », Eur. J. Oper. Res., vol. 260, no 2, p. 482­493, juill. 2017, doi: 10.1016/j.ejor.2017.01.002.
  5. Villa, E. Vallada, et L. Fanjul-Peyro, « Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource », Expert Syst. Appl., vol. 93, p. 28­38, mars 2018, doi: 10.1016/j.eswa.2017.09.054.
  6. L. Daniels, S. Y. Hua, et S. Webster, « Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment », Comput. Oper. Res., vol. 26, no 2, p. 143­155, févr. 1999, doi: 10.1016/S0305-0548(98)00054-9.
  7. Grigoriev, M. Sviridenko, et M. Uetz, « Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times », in Integer Programming and Combinatorial Optimization, vol. 3509, M. Jünger et V. Kaibel, Éd., in Lecture Notes in Computer Science, vol. 3509. , Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, p. 182­195. doi: 10.1007/11496915_14.
  8. Blazewicz, J. K. Lenstra, et A. H. G. R. Kan, « Scheduling subject to resource constraints: classification and complexity », Discrete Appl. Math., vol. 5, no 1, p. 11­24, janv. 1983, doi: 10.1016/0166-218X(83)90012-4.
  9. Wang, C. Xiao, X. Lin, et Y.-Y. Lu, « Single Machine Total Absolute Differences Penalties Minimization Scheduling with a Deteriorating and Resource-Dependent Maintenance Activity », Comput. J., vol. 61, no 1, p. 105­110, janv. 2018, doi: 10.1093/comjnl/bxx044.
  10. Y. Wang et J.-J. Wang, « Single-machine due date assignment problem with deteriorating jobs and resource-dependent processing times », Int. J. Adv. Manuf. Technol., vol. 67, no 1­4, p. 255­260, juill. 2013, doi: 10.1007/s00170-013-4771-x.
  11. Yin, L. Kang, T.-C. Sun, C. Yue, et X.-R. Wang, « Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times », Appl. Math. Model., vol. 38, no 19­20, p. 4747­4755, oct. 2014, doi: 10.1016/j.apm.2014.03.022.
  12. Norelhouda, B. Faycal, et S. Lamia, « Parallel machines scheduling problem with skilled operators in a potery handicraft firm », in 2020 IEEE 13th International Colloquium of Logistics and Supply Chain Management (LOGISTIQUA), Fez, Morocco: IEEE, déc. 2020, p. 1­7. doi: 10.1109/LOGISTIQUA49782.2020.9353923.
  13. Sekkal et F. Belkaid, « A multi-objective simulated annealing to solve an identical parallel machine scheduling problem with deterioration effect and resources consumption constraints », J. Comb. Optim., vol. 40, no 3, p. 660­696, oct. 2020, doi: 10.1007/s10878-020-00607-y.
  14. Hamzadayi et G. Yildiz, « Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times », Comput. Ind. Eng., vol. 106, p. 287­298, avr. 2017, doi: 10.1016/j.cie.2017.02.013.
  15. W. Kim, K.-H. Kim, W. Jang, et F. Frank Chen, « Unrelated parallel machine scheduling with setup times using simulated annealing », Robot. Comput.-Integr. Manuf., vol. 18, no 3­4, p. 223­231, juin 2002, doi: 10.1016/S0736-5845(02)00013-3.
  16. Tigane, M. Dahane, et M. Boudhar, « Multiobjective approach for deteriorating jobs scheduling for a sustainable manufacturing system », Int. J. Adv. Manuf. Technol., vol. 101, no 5­8, p. 1939­1957, avr. 2019, doi: 10.1007/s00170-018-3043-1.
  17. Lei et H. Yang, « Scheduling unrelated parallel machines with preventive maintenance and setup time: Multi-sub-colony artificial bee colony », Appl. Soft Comput., vol. 125, p. 109154, août 2022, doi: 10.1016/j.asoc.2022.109154.
  18. Wang, A. Che, et J. Feng, « Energy-efficient unrelated parallel machine scheduling with general position-based deterioration », Int. J. Prod. Res., vol. 61, no 17, p. 5886­5900, sept. 2023, doi: 10.1080/00207543.2022.2118887.
  19. K. Varadharajan et C. Rajendran, « A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs », Eur. J. Oper. Res., vol. 167, no 3, p. 772­795, déc. 2005, doi: 10.1016/j.ejor.2004.07.020.

International Journal of Scientific Research in Science and Technology

Downloads

Published

2023-12-24

Issue

Volume 10, Issue 14, November-December-2023

Section

Research Articles

License

Copyright (c) IJSRST

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
SEKKAL Norelhouda, SEKKAL Djazia Nadjat, EL OUCHDI Mouna, BELKAID Faycal "Addressing a Complex Manufacturing Problem using Linear Programming Modelization and MOSA Metaheuristic" International Journal of Scientific Research in Science and Technology(IJSRST), Online ISSN : 2395-602X, Print ISSN : 2395-6011,Volume 10, Issue 14, pp.51-60, November-December-2023.