A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem

References

• Allahverdi A. The two- and m-machine flowshop scheduling problems with bicriteria of makespan and mean flowtime. Eur. J. Oper. Res. (2003) 147:373–396Crossref, Google Scholar
• Allahverdi A. A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Comput. Oper. Res. (2004) 31:157–180Crossref, Google Scholar
• Armentano V. A., Arroyo J. E. C. An application of a multiobjective tabu search algorithm to a bicriteria flowshop problem. J. Heuristics (2004) 10:463–481Crossref, Google Scholar
• Arroyo J. E. C., Armentano V. A. A partial enumeration heuristic for multiobjective flowshop scheduling problems. J. Oper. Res. Soc. (2004) 55:1000–1007Crossref, Google Scholar
• Arroyo J. E. C., Armentano V. A. Genetic local search for multiobjective flowshop scheduling problems. Eur. J. Oper. Res. (2005) 167:717–738Crossref, Google Scholar
• Bagchi T. P., Zitzler E., Deb K., Thiele L., Coello Coello C. A., Corne D. Pareto-optimal solutions for multiobjective production scheduling problems. Evolutionary Multicriterion Optim., First Internat. Conf., EMO 2001, Zurich (March 7–9), Proc., Lecture Notes in Computer Science (2001) 1993(Springer, Heidelberg) 458–471Google Scholar
• Basseur M. Conception d'algorithmes coopératifs pour l'optimisation multiobjectif: Application aux problèmes d'ordonnancement de type flow-shop. (2005) . Ph.D. thesis, Laboratoire d'Informatique Fondamentale de Lille, Lille, France. [In French.]Google Scholar
• Cavalieri S., Gaiardelli P. Hybrid genetic algorithms for a multiple-objective scheduling problem. J. Intelligent Manufacturing (1998) 9:361–367Crossref, Google Scholar
• Chakravarthy K., Rajendran C. A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization. Production Planning Control (1999) 10:707–714Crossref, Google Scholar
• Chang P. C., Hsieh J. C., Lin S. G. The development of gradual-priority weighting approach for the multiobjective flowshop scheduling problem. Internat. J. Production Econom. (2002) 79:171–183Crossref, Google Scholar
• Chou F. D., Lee C. E. Two-machine flowshop scheduling with bicriteria problem. Comput. Indust. Engrg. (1999) 36:549–564Crossref, Google Scholar
• Conover W.Practical Nonparametric Statistics (1999) 3rd ed.(John Wiley & Sons, New York) Google Scholar
• Corne D. W., Knowles J. D., Oates M. J., Schoenauer M., Deb K., Rudolph G., Yao X., Lutton E., Merelo Guervós J. J., Schwefel H.-P. The Pareto envelope-based selection algorithm for multiobjective optimization. Parallel Problem Solving from Nature—PPSN VI, 6th Internat. Conf., Paris (September 18–20), Proc., Lecture Notes in Computer Science (2000) 1917(Springer, Heidelberg) 839–848Crossref, Google Scholar
• Corne D. W., Jerram N. R., Knowles J. D., Oates M. J., Spector L., Goodman E. D., Wu A., Langdon W. B., Voigt H.-M., Gen M., Sen S., Dorigo M., Pezeshk S., Garzon M. H., Burke E. PESA-II: Region-based selection in evolutionary multiobjective optimization. Proc. Genetic and Evolutionary Comput. Conf. (GECCO-2001) (2001) San Francisco(Morgan Kaufmann, San Francisco) 283–290Google Scholar
• Daniels R. L., Chambers R. J. Multiobjective flow-shop scheduling. Naval Res. Logist. (1990) 37:981–995Crossref, Google Scholar
• Deb K.Multiobjective Optimization Using Evolutionary Algorithms (2001) (John Wiley & Sons, West Sussex, UK) Google Scholar
• Deb K. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evolutionary Comput. (2002) 6:182–197Crossref, Google Scholar
• Deb K., Mohan M., Mishra S. A fast multiobjective evolutionary algorithm for finding well-spread Pareto-optimal solutions. (2002) . Technical Report 2003002, Kanpur Genetic Algorithms Laboratory (KanGAL), Kanpur, IndiaGoogle Scholar
• Du J., Leung J. Y.-T. Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. (1990) 15:483–495Link, Google Scholar
• El-Bouri A., Balakrishnan S., Popplewell N. A neural network to enhance local search in the permutation flowshop. Comput. Indust. Engrg. (2005) 49:182–196Crossref, Google Scholar
• Framinan J. M., Leisten R. A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness. Internat. J. Production Econom. (2006) 99:28–40Crossref, Google Scholar
• Framinan J. M., Gupta J. N. D., Leisten R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. J. Oper. Res. Soc. (2004) 55:1243–1255Crossref, Google Scholar
• Framinan J. M., Leisten R., Ruiz-Usano R. Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. Eur. J. Oper. Res. (2002) 141:559–569Crossref, Google Scholar
• Gangadharan R., Rajendran C. A simulated annealing heuristic for scheduling in a flowshop with bicriteria. Comput. Indust. Engrg. (1994) 27:473–476Crossref, Google Scholar
• Garey M. R., Johnson D. S., Sethi R. The complexity of flowshop and jobshop scheduling. Math. Oper. Res. (1976) 1:117–129Link, Google Scholar
• Geiger M. J. On operators and search space topology in multiobjective flow shop scheduling. Eur. J. Oper. Res. (2007) 181:195–206Crossref, Google Scholar
• Gonzalez T., Sahni S. Flowshop and jobshop schedules: Complexity and approximation. Oper. Res. (1978) 26:36–52Link, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Gupta J. N. D., Hennig K., Werner F. Local search heuristics for two-stage flow shop problems with secondary criterion. Comput. Oper. Res. (2002) 29:123–149Crossref, Google Scholar
• Gupta J. N. D., Neppalli V. R., Werner F. Minimizing total flow time in a two-machine flowshop problem with minimum makespan. Internat. J. Production Econom. (2001) 69:323–338Crossref, Google Scholar
• Gupta J. N. D., Palanimuthu N., Chen C. L. Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion. Production Planning Control (1999) 10:251–265Crossref, Google Scholar
• Hasija S., Rajendran C. Scheduling in flowshops to minimize total tardiness of jobs. Internat. J. Production Res. (2004) 42:2289–2301Crossref, Google Scholar
• Hejazi S. R., Saghafian S. Flowshop-scheduling problems with makespan criterion: A review. Internat. J. Production Res. (2005) 43:2895–2929Crossref, Google Scholar
• Ho J. C., Chang Y.-L. A new heuristic for the n-job, M-machine flow-shop problem. Eur. J. Oper. Res. (1991) 52:194–202Crossref, Google Scholar
• Hoogeveen H. Multicriteria scheduling. Eur. J. Oper. Res. (2005) 167:592–623Crossref, Google Scholar
• Ishibuchi H., Murata T. A multiobjective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans. Systems Man Cybernetics (1998) 28:392–403Crossref, Google Scholar
• Ishibuchi H., Yoshida T., Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. Evolutionary Comput. (2003) 7:204–223Crossref, Google Scholar
• Johnson S. M. Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. Quart. (1954) 1:61–68Crossref, Google Scholar
• Jones D. F., Mirrazavi S. K., Tamiz M. Multiobjective meta-heuristics: An overview of the current state-of-the-art. Eur. J. Oper. Res. (2002) 137:1–9Crossref, Google Scholar
• Knowles J., Corne D. W. Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Comput. (2000) 8:149–172Crossref, Google Scholar
• Knowles J., Thiele L., Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. (2006) . Technical Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich. [Revised version.]Google Scholar
• Kollat J. B., Reed P. M., Coello Coello C. A., Hernández Aguirre A., Zitzler E. The value of online adaptive search: A performance comparison of nsgaii, ε-nsgaii, and ε-moea. Evolutionary Multicriterion Optim., Third Internat. Conf., EMO 2005, Guanajuato, Mexico (March 9–11), Proc., Lecture Notes in Computer Science (2005) 3410(Springer, Heidelberg) 386–398Crossref, Google Scholar
• Lee C. E., Chou F. D. A two-machine flowshop scheduling heuristic with bicriteria objective. Internat. J. Indust. Engrg. (1998) 5:128–139Google Scholar
• Lee W. C., Wu C. C. Minimizing the total flow time and the tardiness in a two-machine flow shop. Internat. J. Systems Sci. (2001) 32:365–373Crossref, Google Scholar
• Lemesre J., Dhaenens C., Talbi E. G. An exact parallel method for a biobjective permutation flowshop problem. Eur. J. Oper. Res. (2007) 177:1641–1655Crossref, Google Scholar
• Liao C.-J., Yu W.-C., Joe C.-B. Bicriterion scheduling in the two-machine flowshop. J. Oper. Res. Soc. (1997) 48:929–935Crossref, Google Scholar
• Lin B. M. T., Wu J. M. Bicriteria scheduling in a two-machine permutation flowshop. Internat. J. Production Res. (2006) 44:2299–2312Crossref, Google Scholar
• Loukil T., Teghem J., Fortemps P. Solving multiobjective production scheduling problems with tabu search. Control Cybernetics (2000) 29:819–828Google Scholar
• Loukil T., Teghem J., Tuyttens D. Solving multiobjective production scheduling problems using metaheuristics. Eur. J. Oper. Res. (2005) 161:42–61Crossref, Google Scholar
• Melab N., Mezmaz M., Talbi E. G. Parallel cooperative meta-heuristics on the computational grid. A case study: The biobjective flow-shop problem. Parallel Comput. (2006) 32:643–659Crossref, Google Scholar
• Montgomery D. C.Design and Analysis of Experiments (2004) 6th ed.(John Wiley & Sons, New York) Google Scholar
• Murata T., Ishibuchi H., Gen M., Zitzler E., Deb K., Thiele L., Coello Coello C. A., Corne D. Specification of genetic search directions in cellular multiobjective genetic algorithms. Evolutionary Multicriterion Optim., First Internat. Conf., EMO 2001, Zurich (March 7–9), Proc., Lecture Notes in Computer Science (2001) 1993(Springer, Heidelberg) 82–95Google Scholar
• Murata T., Ishibuchi H., Tanaka H. Multiobjective genetic algorithm and its applications to flowshop scheduling. Comput. Indust. Engrg. (1996) 30:957–968Crossref, Google Scholar
• Nagar A., Heragu S. S., Haddock J. A branch-and-bound approach for a two-machine flowshop scheduling problem. J. Oper. Res. Soc. (1995a) 46:721–734Crossref, Google Scholar
• Nagar A., Heragu S. S., Haddock J. Mutiple and bicriteria scheduling: A lierature survey. Eur. J. Oper. Res. (1995b) 81:88–104Crossref, Google Scholar
• Nagar A., Heragu S. S., Haddock J. A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem. Ann. Oper. Res. (1996) 63:397–414Crossref, Google Scholar
• Nawaz M., Enscore Jr. E. E., Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, Internat. J. Management Sci. (1983) 11:91–95Crossref, Google Scholar
• Neppalli V. R., Chen C.-L., Gupta J. N. D. Genetic algorithms for the two-stage bicriteria flowshop problem. Eur. J. Oper. Res. (1996) 95:356–373Crossref, Google Scholar
• Paquete L. F. Stochastic local search algorithms for multiobjective combinatorial optimization: Method and analysis. (2005) . Ph.D. thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, GermanyGoogle Scholar
• Pasupathy T., Rajendran C., Suresh R. K. A multiobjective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. Internat. J. Adv. Manufacturing Tech. (2006) 27:804–815Crossref, Google Scholar
• Ponnambalam S. G., Jagannathan H., Kataria M., Gadicherla A. A TSP-GA multiobjective algorithm for flow-shop scheduling. Internat. J. Adv. Manufacturing Tech. (2004) 23:909–915Crossref, Google Scholar
• Rahimi-Vahed A. R., Mirghorbani S. M. A multiobjective particle swarm for a flow shop scheduling problem. J. Combin. Optim. (2007) 13:79–102Crossref, Google Scholar
• Rajendran C. Two-stage flowshop scheduling problem with bicriteria. J. Oper. Res. Soc. (1992) 43:871–884Crossref, Google Scholar
• Rajendran C. A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multicriteria. Internat. J. Production Res. (1994) 32:2541–2558Crossref, Google Scholar
• Rajendran C. Heuristics for scheduling in flowshop with multiple objectives. Eur. J. Oper. Res. (1995) 82:540–555Crossref, Google Scholar
• Rajendran C., Ziegler H. Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Comput. Indust. Engrg. (2005) 48:789–797Crossref, Google Scholar
• Ravindran D., Haq A. N., Selvakuar S. J., Sivaraman R. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. Internat. J. Adv. Manufacturing Tech. (2005) 25:1007–1012Crossref, Google Scholar
• Ruiz R., Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics. Eur. J. Oper. Res. (2005) 165:479–494Crossref, Google Scholar
• Sayın S., Karabatı S. A bicriteria approach to the two-machine flow shop scheduling problem. Eur. J. Oper. Res. (1999) 113:435–449Crossref, Google Scholar
• Schaffer J. D. Multiple objective optimization with vector evaluated genetic algorithms. Proc. 1st Internat. Conf. Genetic Algorithms, Pittsburgh (1985) (Lawrence Erlbaum Associates, Inc., Mahwah, NJ) 93–100Google Scholar
• Selen W. J., Hott D. D. A mixed-integer goal-programming formulation of the standard flowshop scheduling problem. J. Oper. Res. Soc. (1986) 37:1121–1128Crossref, Google Scholar
• Sivrikaya-Şerifoğlu F., Ulusoy G. A bicriteria two-machine permutation flowshop problem. Eur. J. Oper. Res. (1998) 107:414–430Crossref, Google Scholar
• Sridhar J., Rajendran C. Scheduling in flowshop and cellular manufacturing systems with multiple objectives: A genetic algorithmic approach. Production Planning Control (1996) 7:374–382Crossref, Google Scholar
• Srinivas N., Deb K. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Comput. (1994) 2:221–248Crossref, Google Scholar
• Suresh R. K., Mohanasundaram K. M. Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives. Proc. IEEE Conf. Cybernetics and Intelligent Systems (CIS) (2004) 2Singapore(Institute of Electrical and Electronics Engineers, Washington, D.C.) 712–717Crossref, Google Scholar
• Taillard E. Benchmarks for basic scheduling problems. Eur. J. Oper. Res. (1993) 64:278–285Crossref, Google Scholar
• T'kindt V., Billaut J.-C. Multicriteria scheduling problems: A survey. RAIRO Recherche opérationnelle—Oper. Res. (2001) 35:143–163Crossref, Google Scholar
• T'kindt V., Billaut J.-C.Multicriteria Scheduling: Theory, Models and Algorithms (2002) (Springer, Berlin) Crossref, Google Scholar
• T'kindt V., Gupta J. N. D., Billaut J.-C. Two-machine flowshop scheduling with a secondary criterion. Comput. Oper. Res. (2003) 30:505–526Crossref, Google Scholar
• T'kindt V., Monmarché N., Tercinet F., Laügt D. An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. Eur. J. Oper. Res. (2002) 142:250–257Crossref, Google Scholar
• Toktaş B., Azizoğlu M., Köksalan S. K. Two-machine flow shop scheduling with two criteria: Maximum earliness and makespan. Eur. J. Oper. Res. (2004) 157:286–295Crossref, Google Scholar
• Vallada E., Ruiz R., Minella G. Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Comput. Oper. Res. (2008) 35:1350–1373Crossref, Google Scholar
• Varadharajan T. K., Rajendran C. A multiobjective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. Eur. J. Oper. Res. (2005) 167:772–795Crossref, Google Scholar
• Wilson J. M. Alternative formulations of a flowshop scheduling problem. J. Oper. Res. Soc. (1989) 40:395–399Crossref, Google Scholar
• Yeh W.-C. A new branch-and-bound approach for the n/2/flowshop/α F + β Cmax. Comput. Oper. Res. (1999) 26:1293–1310Crossref, Google Scholar
• Yeh W.-C. An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem. J. Manufacturing Systems (2001) 20:113–123Crossref, Google Scholar
• Yeh W.-C. A memetic algorithm for the n/2/flowshop/α F + β Cmax scheduling problem. Internat. J. Adv. Manufacturing Tech. (2002) 20:464–473Crossref, Google Scholar
• Zitzler E., Künzli S. Indicator-based selection in multiobjective search. 8th Internat. Conf. Parallel Problem Solving from Nature (PPSN VIII) (2004) Birmingham, UK(Springer-Verlag, Berlin) 832–842Crossref, Google Scholar
• Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. Evolutionary Comput. (1999) 3:257–271Crossref, Google Scholar
• Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. (2001) . Technical Report 103, Computer Engineering and Networks Laboratory (TIK), ETH ZurichGoogle Scholar
• Zitzler E., Thiele L., Laumanns M., Fonseca C. M., da Fonseca V. G. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. Evolutionary Comput. (2003) 7:117–132Crossref, Google Scholar