A Multiobjective Optimization Approach to Solve a Parallel Machines Scheduling Problem

Advances in Artificial Intelligence

Research Article

Hicham Chehade¹  Farouk Yalaoui¹  Lionel Amodeo¹  Xiaohui Li¹ 

[1] Université de Technologie de Troyes, Institut Charles Delaunay, LOSI (UMR-STMR 6279), 12 Rue Marie Curie BP 2060 10010 Troyes Cedex, France, utt.fr

Others  :  1266135
DOI  :  10.1155/2010/943050

 received in 2010-03-23, accepted in 2010-10-27,  发布年份 2010

【 授权许可】

CC BY   
Copyright © 2010 Xiaohui Li et al. 2010

【 图 表 】

Figure 1

Figure 2

【 参考文献 】

• [1]R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan. et al.(1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics.5(C):287-326. DOI: 10.1016/S0167-5060(08)70356-X.
• [2]T. C. E. Cheng, C. C. S. Sin. (1990). A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research.47(3):271-292. DOI: 10.1016/S0167-5060(08)70356-X.
• [3]P. Brucker. (1998). Scheduling Algorithm. DOI: 10.1016/S0167-5060(08)70356-X.
• [4]M. Gendreau, G. Laporte, E. M. Guimarães. (2001). A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times. European Journal of Operational Research.133(1):183-189. DOI: 10.1016/S0167-5060(08)70356-X.
• [5]F. Yalaoui, C. Chu. (2003). An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Transactions.35(2):183-190. DOI: 10.1016/S0167-5060(08)70356-X.
• [6]A. Gharbi, M. Haouari. (2002). Minimizing makespan on parallel machines subject to release dates and delivery times. Journal of Scheduling.5(4):329-355. DOI: 10.1016/S0167-5060(08)70356-X.
• [7]E. Néron, F. Tercinet, F. Sourd. (2008). Search tree based approaches for parallel machine scheduling. Computers and Operations Research.35(4):1127-1137. DOI: 10.1016/S0167-5060(08)70356-X.
• [8]M. Zouba, P. Baptiste, D. Rebaine. (2009). Scheduling identical parallel machines and operators within a period based changing mode. Computers and Operations Research.36(12):3231-3239. DOI: 10.1016/S0167-5060(08)70356-X.
• [9]L. Fanjul-Peyro, R. Ruiz. (2011). Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers and Operations Research.38(1):301-309. DOI: 10.1016/S0167-5060(08)70356-X.
• [10]C. Koulamas. (1994). Total tardiness problem: review and extensions. Operations Research.42(6):1025-1041. DOI: 10.1016/S0167-5060(08)70356-X.
• [11]M. Azizoglu, O. Kirca. (1998). Tardiness minimization on parallel machines. International Journal of Production Economics.55(2):163-168. DOI: 10.1016/S0167-5060(08)70356-X.
• [12]F. Yalaoui, C. Chu. (2002). Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics.76(3):265-279. DOI: 10.1016/S0167-5060(08)70356-X.
• [13]S.-O. Shim, Y.-D. Kim. (2007). Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research.177(1):135-146. DOI: 10.1016/S0167-5060(08)70356-X.
• [14]S.-O. Shim, Y.-D. Kim. (2008). A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Computers and Operations Research.35(3):863-875. DOI: 10.1016/S0167-5060(08)70356-X.
• [15]N. Huynh Tuong, A. Soukhal, J.-C. Billaut. (2010). A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines. European Journal of Operational Research.202(3):646-653. DOI: 10.1016/S0167-5060(08)70356-X.
• [16]A. A. B. Pritsker, L. J. Walters, P. M. Wolf. (1969). Multi-project scheduling with limited resources: a zero-one programming approach. Management Science.16:93-108. DOI: 10.1016/S0167-5060(08)70356-X.
• [17]B. Alidaee, D. Rosa. (1997). Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers and Operations Research.24(8):775-788. DOI: 10.1016/S0167-5060(08)70356-X.
• [18]K. R. Baker, J. W. M. Bertrand. (1982). A dynamic priority rule for scheduling against due-dates. Journal of Operations Management.3(1):37-42. DOI: 10.1016/S0167-5060(08)70356-X.
• [19]J. Lamothe, F. Marmier, M. Dupuy, P. Gaborit. et al.Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints. . DOI: 10.1016/S0167-5060(08)70356-X.
• [20]J. D. Schaffer. Multiple objective optimization with vector evaluated genetic algorithms. :93-100. DOI: 10.1016/S0167-5060(08)70356-X.
• [21]F. Kursame. A variant of evolution strategies for vector optimization. .496:193-197. DOI: 10.1016/S0167-5060(08)70356-X.
• [22]P. Hajela, C.-Y. Lin. (1992). Genetic search strategies in multicriterion optimal design. Structural Optimization.4(2):99-107. DOI: 10.1016/S0167-5060(08)70356-X.
• [23]C. M. Fonseça, P. J. Fleming. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. :416-423. DOI: 10.1016/S0167-5060(08)70356-X.
• [24]J. Horn, N. Nafpliotis, D. E. Goldberg. Niched Pareto genetic algorithm for multiobjective optimization. .1:82-87. DOI: 10.1016/S0167-5060(08)70356-X.
• [25]K. Deb, S. Agrawal, A. Pratap, T. Meyarivan. et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. :849-858. DOI: 10.1016/S0167-5060(08)70356-X.
• [26]E. Zitzler, M. Laumanns, L. Thiele. (2001). SPEA2: improving the strength pareto evolutionary algorithm. (103). DOI: 10.1016/S0167-5060(08)70356-X.
• [27]J. D. Knowles, D. W. Corne. (2000). Approximating the nondominated front using the Pareto Archived Evolution Strategy. Evolutionary computation.8(2):149-172. DOI: 10.1016/S0167-5060(08)70356-X.
• [28]D. W. Corne, J. D. Knowles, M. J. Oates. The Pareto envelope based selection algorithm for multiobjective optimization. :839-848. DOI: 10.1016/S0167-5060(08)70356-X.
• [29]J. K. Cochran, S.-M. Horng, J. W. Fowler. (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers and Operations Research.30(7):1087-1102. DOI: 10.1016/S0167-5060(08)70356-X.
• [30]P.-C. Chang, S.-H. Chen, K.-L. Lin. (2005). Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications.29(3):705-712. DOI: 10.1016/S0167-5060(08)70356-X.
• [31]P.-C. Chang, S.-H. Chen, J.-C. Hsieh. A global archive sub-population genetic algorithm with adaptive strategy in multi-objective parallel-machine scheduling problem. .4221:730-739. DOI: 10.1016/S0167-5060(08)70356-X.
• [32]F. Baesler, R. Moraga, O. Cornejo. (2008). Introduction of memory elements in simulated annealing method to solve multiobjective parallel machine scheduling problems. Ingeniare.16(3):428-437. DOI: 10.1016/S0167-5060(08)70356-X.
• [33]F. Baesler, L. Ceballos, M. Ramírez. (2006). Multiobjecttve molding machine scheduling using memetic algorithms. Maderas: Ciencia y Tecnologia.8(3):183-192. DOI: 10.1016/S0167-5060(08)70356-X.
• [34]K. Bouibede-Hocine, V. T’kindt, D. Tran. Two evolutionary algorithms for a uniform parallel machines. . DOI: 10.1016/S0167-5060(08)70356-X.
• [35]F. Dugardin, H. Chehade, L. Amodeo, F. Yalaoui. et al.(2007). Hybrid Job Shop and parallel machine scheduling problems: minimization of total tardiness criterion. Multiprocessor Scheduling: Theory and Applications:436. DOI: 10.1016/S0167-5060(08)70356-X.
• [36]J. Gao, G. He, Y. Wang. (2009). A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint. International Journal of Advanced Manufacturing Technology.43(1-2):151-160. DOI: 10.1016/S0167-5060(08)70356-X.
• [37]J. Gao. (2010). A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint. Computers and Industrial Engineering.58(4):602-609. DOI: 10.1016/S0167-5060(08)70356-X.
• [38]Z. Fang. An improved weight-based multiobjective genetic algorithm and its application to parallel machine scheduling. .1:161-164. DOI: 10.1016/S0167-5060(08)70356-X.
• [39]Z. Lian. (2010). A united search particle swarm optimization algorithm for multiobjective scheduling problem. Applied Mathematical Modelling.34(11):3518-3526. DOI: 10.1016/S0167-5060(08)70356-X.
• [40]C.-C. Chyu, W.-S. Chang. (2010). A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems. International Journal of Advanced Manufacturing Technology.49(5–8):697-708. DOI: 10.1016/S0167-5060(08)70356-X.
• [41]X. Li, F. Yalaoui, L. Amodeo, A. et Hamzaoui. et al.Multiobjective method to solve a parallel machine scheduling problem. . DOI: 10.1016/S0167-5060(08)70356-X.
• [42]R. Nessah, C. Chu, F. Yalaoui. (2007). An exact method for Pm/sds, ri/ problem. Computers and Operations Research.34(9):2840-2848. DOI: 10.1016/S0167-5060(08)70356-X.
• [43]S. V. Kumar, S. R. Ranjithan. Evaluation of the Constraint Method-based Multiobjective Evolutionary Algorithm (CMEA) for a three objective optimization problem. :431-438. DOI: 10.1016/S0167-5060(08)70356-X.
• [44]E. Zitzler, L. Thiele. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation.3(4):257-271. DOI: 10.1016/S0167-5060(08)70356-X.
• [45]S. R. Ranjithan, S. K. Chetan, H. K. Dakshina. (2001). Constraint method-based evolutionary algorithm (CMEA) for multiobjective optimization. Evolutionary Multi-Criteria Optimization:299-313. DOI: 10.1016/S0167-5060(08)70356-X.
• [46]D. A. VanVeldhuizen. (1999). Multiobjective evolutionary algorithms: classification, analyses, and new innovations, Ph.D. thesis. DOI: 10.1016/S0167-5060(08)70356-X.
• [47]A. Riise. Comparing genetic algorithms and tabu search for multi-objective optimization. :29. DOI: 10.1016/S0167-5060(08)70356-X.