×

A multi-objective production scheduling case study solved by simulated annealing. (English) Zbl 1163.90498

Summary: During several decades, research in production scheduling mainly concerns a single criterion to optimize. However, the analysis of the performance of a schedule often involves more than one aspect and therefore requires multi-objective analysis. Such situation appears in the real case study considered here.
This paper deals with a production scheduling problem in a flexible (or hybrid) job-shop with particular constraints: batch production; existence of two steps: production of several sub-products followed by the assembly of the final product; possible overlaps for the processing periods of two successive operations of a same job. At the end of the production step, different objectives should be considered simultaneously, among the makespan, the mean completion time, the maximal tardiness, the mean tardiness. The research is based on a real case study, concerning a Tunisian firm. We propose a multi-objective simulated annealing approach to tackle this problem and to propose to the manager an approximation of the set of efficient schedules.Several numerical results are reported.

MSC:

90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dauzère-Pérès, S.; Paulli, J., An integrated approach for modelling and solving the general multiprocessor job-shop scheduling problem using Tabu search, Annals of Operations Research, 70, 281-306 (1997) · Zbl 0890.90097
[2] Ehrgott, M.; Gandibleux, X., Multiobjective combinatorial optimization—theory, methodology and applications, (Ehrgott, M.; Gandibleux, X., Multiple Criteria Optimization. State of the Art. Annotated Bibliographic. Surveys (2002), Kluwer) · Zbl 1095.90593
[3] El Maqrini, H.; Teghem, J., Efficiency of metaheuristics to schedule a general job-shop, Belgian Journal of Operations Research (JORBEL, 41, 1-25, 83-102 (2001) · Zbl 1066.90522
[4] Glover, F.; Kochenberger, G. A., Handbook of Metaheuristics (2003), Kluwer · Zbl 1058.90002
[5] Haouari, M.; Daouas, T., Optimal scheduling of the 3—machine assembly—type flow shop, RAIRO Recherche Opérationnelle, 33, 4, 439-445 (1999) · Zbl 0961.90033
[6] Jansen, K.; Mastrolilli, M.; Solis-Oba, R., Approximation algorithms for flexible job-shop problems, (Proceedings of Latin American Theoretical Informatics (Latin’ 2000). Proceedings of Latin American Theoretical Informatics (Latin’ 2000), LNCS, 1776 (1999), Springer), 68-77 · Zbl 0959.68009
[7] A. Jaszkiewicz, J. Teghem, Multiple objective metaheuristics for combinatorial optimization, a review. Technical report, Poznan University of Technology, 2002.; A. Jaszkiewicz, J. Teghem, Multiple objective metaheuristics for combinatorial optimization, a review. Technical report, Poznan University of Technology, 2002.
[8] Kacem, I.; Hammadi, S.; Borne, P., Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic, Mathematics and Computers in Simulation, 60, 3-5, 245-276 (2002) · Zbl 1006.90044
[9] Loukil, T.; Teghem, J.; Tuyttens, D., Solving multi-objective production scheduling problems using metaheuristics, European Journal of Operational Research, 161, 42-61 (2005) · Zbl 1065.90040
[10] Loukil, T.; Teghem, J.; Fortemps, Ph., Solving multi-objective production scheduling problems with tabu-search, Control and Cybernetics, 29, 3, 819-828 (2000) · Zbl 0992.90074
[11] T. Loukil, J. Teghem, A review of multi-objective production scheduling, Technical report, Faculté Polytechnique de Mons, 2004.; T. Loukil, J. Teghem, A review of multi-objective production scheduling, Technical report, Faculté Polytechnique de Mons, 2004.
[12] Mastrolilli, M.; Gambardella, J. M., Effective neighboorhood functions for the flexible job shop problem, Journal of Scheduling, 3, 1, 30020 (2000)
[13] Teghem, J.; Tuyttens, D.; Ulungu, E. L., An interactive heuristic method for multi-objective combinatorial optimization, Computers and Operations Research, 27, 621-634 (2000) · Zbl 0961.90104
[14] J. Teghem, M. Pirlot, Optimisation approchée en recherche opérationnelle. Collection IC2, Hermès, 2002.; J. Teghem, M. Pirlot, Optimisation approchée en recherche opérationnelle. Collection IC2, Hermès, 2002.
[15] T’Kindt, V.; Billaut, J.-Ch., Multicriteria Scheduling (Theory, Models and Algorithms) (2002), Springer
[16] Tuyttens, D.; Teghem, J.; Fortemps, Ph.; Van Nieuwenhuyse, K., Performance of the MOSA method for the bicriteria assignment problem, Journal of Heuristics, 6, 295-310 (2000) · Zbl 1071.90567
[17] E.L. Ulungu, J. Teghem, Ph. Fortemps, Heuristic for multi-objective combinatorial optimization problems by simulated annealing, in: J. Gu, G. Chen, Q. Wei, S. Wang (Eds), MCDM: Theory and Applications, Sci-Tech, 1995, 229-238.; E.L. Ulungu, J. Teghem, Ph. Fortemps, Heuristic for multi-objective combinatorial optimization problems by simulated annealing, in: J. Gu, G. Chen, Q. Wei, S. Wang (Eds), MCDM: Theory and Applications, Sci-Tech, 1995, 229-238.
[18] Ulungu, E. L.; Teghem, J.; Fortemps, Ph.; Tuyttens, D., MOSA method: A tool for solving MOCO problems, Journal of Multi-Criteria Decision Analysis, 8, 221-236 (1999) · Zbl 0935.90034
[19] Van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing; Theory and Practice (1987), Kluwer · Zbl 0643.65028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.