IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v60y2002i3p245-276.html
   My bibliography  Save this article

Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic

Author

Listed:
  • Kacem, Imed
  • Hammadi, Slim
  • Borne, Pierre

Abstract

Most scheduling problems are complex combinatorial problems and very difficult to solve [Manage. Sci. 35 (1989) 164; F.S. Hillier, G.J. Lieberman, Introduction to Operations Research, Holden-Day, San Francisco, CA, 1967]. That is why, lots of methods focus on the optimization according to a single criterion (makespan, workloads of machines, waiting times, etc.). The combining of several criteria induces additional complexity and new problems. In this paper, we propose a Pareto approach based on the hybridization of fuzzy logic (FL) and evolutionary algorithms (EAs) to solve the flexible job-shop scheduling problem (FJSP). This hybrid approach exploits the knowledge representation capabilities of FL [Fuzzy Sets Syst. 1 (1989)] and the adaptive capabilities of EAs. The integration of these two methodologies for the multi-objective optimization has become an increasing interest. The objective considered is to minimize the overall completion time (makespan), the total workload of machines and the workload of the most loaded machine. Many examples are presented to illustrate some theoretical considerations and to show the efficiency of the suggested methodology.

Suggested Citation

  • Kacem, Imed & Hammadi, Slim & Borne, Pierre, 2002. "Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 60(3), pages 245-276.
    • Handle: RePEc:eee:matcom:v:60:y:2002:i:3:p:245-276
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378475402000198
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. J. Carlier & E. Pinson, 1989. "An Algorithm for Solving the Job-Shop Problem," Management Science, INFORMS, vol. 35(2), pages 164-176, February.
    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. Po-Hsiang Lu & Muh-Cherng Wu & Hao Tan & Yong-Han Peng & Chen-Fu Chen, 2018. "A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 19-34, January.
    2. Wei Xiong & Dongmei Fu, 2018. "A new immune multi-agent system for the flexible job shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 29(4), pages 857-873, April.
    3. Li-Ning Xing & Ying-Wu Chen & Ke-Wei Yang, 2011. "Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems," Computational Optimization and Applications, Springer, vol. 48(1), pages 139-155, January.
    4. Bingke Yan & Bo Wang & Lin Zhu & Hesen Liu & Yilu Liu & Xingpei Ji & Dichen Liu, 2015. "A Novel, Stable, and Economic Power Sharing Scheme for an Autonomous Microgrid in the Energy Internet," Energies, MDPI, vol. 8(11), pages 1-24, November.
    5. Miguel A. Fernández Pérez & Fernanda M. P. Raupp, 2016. "A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 409-416, April.
    6. Raja Awais Liaqait & Shermeen Hamid & Salman Sagheer Warsi & Azfar Khalid, 2021. "A Critical Analysis of Job Shop Scheduling in Context of Industry 4.0," Sustainability, MDPI, vol. 13(14), pages 1-19, July.
    7. Xiong, Jian & Xing, Li-ning & Chen, Ying-wu, 2013. "Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns," International Journal of Production Economics, Elsevier, vol. 141(1), pages 112-126.
    8. Zhang, Sicheng & Li, Xiang & Zhang, Bowen & Wang, Shouyang, 2020. "Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system," European Journal of Operational Research, Elsevier, vol. 283(2), pages 441-460.
    9. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    10. Saad, Ihsen & Hammadi, Slim & Benrejeb, Mohamed & Borne, Pierre, 2008. "Choquet integral for criteria aggregation in the flexible job-shop scheduling problems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 76(5), pages 447-462.
    11. Vilcot, Geoffrey & Billaut, Jean-Charles, 2008. "A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 190(2), pages 398-411, October.
    12. Abdelmaguid, Tamer F., 2015. "A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 260(C), pages 188-203.
    13. Yiyi Xu & M’hammed Sahnoun & Fouad Ben Abdelaziz & David Baudry, 2022. "A simulated multi-objective model for flexible job shop transportation scheduling," Annals of Operations Research, Springer, vol. 311(2), pages 899-920, April.
    14. Alper Türkyılmaz & Özlem Şenvar & İrem Ünal & Serol Bulkan, 2020. "A research survey: heuristic approaches for solving multi objective flexible job shop problems," Journal of Intelligent Manufacturing, Springer, vol. 31(8), pages 1949-1983, December.
    15. Moslehi, Ghasem & Mahnam, Mehdi, 2011. "A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search," International Journal of Production Economics, Elsevier, vol. 129(1), pages 14-22, January.
    16. Chiang, Tsung-Che & Lin, Hsiao-Jou, 2013. "A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling," International Journal of Production Economics, Elsevier, vol. 141(1), pages 87-98.
    17. Al-Hinai, Nasr & ElMekkawy, T.Y., 2011. "Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm," International Journal of Production Economics, Elsevier, vol. 132(2), pages 279-291, August.
    18. Miguel A. Ortíz & Leidy E. Betancourt & Kevin Parra Negrete & Fabio Felice & Antonella Petrillo, 2018. "Dispatching algorithm for production programming of flexible job-shop systems in the smart factory industry," Annals of Operations Research, Springer, vol. 264(1), pages 409-433, May.
    19. Ho, Nhu Binh & Tay, Joc Cing & Lai, Edmund M.-K., 2007. "An effective architecture for learning and evolving flexible job-shop schedules," European Journal of Operational Research, Elsevier, vol. 179(2), pages 316-333, June.
    20. J. Behnamian, 2016. "Survey on fuzzy shop scheduling," Fuzzy Optimization and Decision Making, Springer, vol. 15(3), pages 331-366, September.
    21. Baykasoglu, Adil & ÖzbakIr, Lale, 2010. "Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system," International Journal of Production Economics, Elsevier, vol. 124(2), pages 369-381, April.
    22. Loukil, Taicir & Teghem, Jacques & Fortemps, Philippe, 2007. "A multi-objective production scheduling case study solved by simulated annealing," European Journal of Operational Research, Elsevier, vol. 179(3), pages 709-722, June.
    23. Julien Autuori & Faicel Hnaien & Farouk Yalaoui, 2016. "A mapping technique for better solution exploration: NSGA-II adaptation," Journal of Heuristics, Springer, vol. 22(1), pages 89-123, February.
    24. Dauzère-Pérès, Stéphane & Ding, Junwen & Shen, Liji & Tamssaouet, Karim, 2024. "The flexible job shop scheduling problem: A review," European Journal of Operational Research, Elsevier, vol. 314(2), pages 409-432.

    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. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    2. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    3. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    4. Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    5. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    6. Mukherjee, Saral & Chatterjee Ashis K, 2002. "Applying Machine Based Decomposition in 2-Machine Flow Shops," IIMA Working Papers WP2002-08-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    8. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    9. Guinet, Alain & Legrand, Marie, 1998. "Reduction of job-shop problems to flow-shop problems with precedence constraints," European Journal of Operational Research, Elsevier, vol. 109(1), pages 96-110, August.
    10. Monaci, Marta & Agasucci, Valerio & Grani, Giorgio, 2024. "An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents," European Journal of Operational Research, Elsevier, vol. 312(3), pages 910-926.
    11. Chen, Haoxun & Luh, Peter B., 2003. "An alternative framework to Lagrangian relaxation approach for job shop scheduling," European Journal of Operational Research, Elsevier, vol. 149(3), pages 499-512, September.
    12. Sheen, Gwo-Ji & Liao, Lu-Wen, 2007. "A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags," European Journal of Operational Research, Elsevier, vol. 181(1), pages 102-116, August.
    13. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    14. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    15. Baptiste, Philippe & Peridy, Laurent & Pinson, Eric, 2003. "A branch and bound to minimize the number of late jobs on a single machine with release time constraints," European Journal of Operational Research, Elsevier, vol. 144(1), pages 1-11, January.
    16. El-Bouri, A. & Azizi, N. & Zolfaghari, S., 2007. "A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1894-1910, March.
    17. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    18. Abdelhakim AitZai & Brahim Benmedjdoub & Mourad Boudhar, 2016. "Branch-and-bound and PSO algorithms for no-wait job shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(3), pages 679-688, June.
    19. Zapfel, G. & Wasner, M., 2000. "A heuristic solution concept for a generalized machine sequencing problem with an application to radiator manufacturing," International Journal of Production Economics, Elsevier, vol. 68(2), pages 199-213, November.
    20. Ouenniche, J. & Bertrand, J. W. M., 2001. "The finite horizon economic lot sizing problem in job shops: : the multiple cycle approach," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 49-61, December.

    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:matcom:v:60:y:2002:i:3:p:245-276. 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.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    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.