Multi-objective Optimization of the Distributed Permutation Flow Shop Scheduling Problem with Transportation and Eligibility Constraints

被引：28
作者：
Cai S. [1 ,2 ]
Yang K. [1 ,2 ]
Liu K. [1 ,2 ,3 ,4 ]
机构：
[1] Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing
[2] University of Chinese Academy of Sciences, Beijing
[3] Key Laboratory of Management, Decision and Information Systems, Chinese Academy of Sciences, Beijing
[4] National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences, Beijing
来源：
Journal of the Operations Research Society of China | 2018年 / 6卷 / 3期
基金：
中国国家自然科学基金;
关键词：
Distributed scheduling; Multi-objective optimization; NSGA-II; Permutation flow shop scheduling; Transportation;
D O I：
10.1007/s40305-017-0165-3
中图分类号：
学科分类号：
摘要：
In this paper, we consider the distributed permutation flow shop scheduling problem (DPFSSP) with transportation and eligibility constrains. Three objectives are taken into account, i.e., makespan, maximum lateness and total costs (transportation costs and setup costs). To the best of our knowledge, there is no published work on multi-objective optimization of the DPFSSP with transportation and eligibility constraints. First, we present the mathematics model and constructive heuristics for single objective; then, we propose an improved The Nondominated Sorting Genetic Algorithm II (NSGA-II) for the multi-objective DPFSSP to find Pareto optimal solutions, in which a novel solution representation, a new population re-/initialization, effective crossover and mutation operators, as well as local search methods are developed. Based on extensive computational and statistical experiments, the proposed algorithm performs better than the well-known NSGA-II and the Strength Pareto Evolutionary Algorithm 2 (SPEA2). © 2017, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.
引用
收藏
页码：391 / 416
页数：25
相关论文
共 58 条
  • [1] Pinedo M., Scheduling: Theory, Algorithms, and Systems, (2015)
  • [2] Garey M.R., Johnson D.S., Sethi R., The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1, 2, pp. 117-129, (1976)
  • [3] Johnson S.M., Optimal two-and three-stage production schedules with setup times included, Nav. Res. Logist. (NRL), 1, 1, pp. 61-68, (1954)
  • [4] Palmer D.S., Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum, J. Oper. Res. Soc., 16, 1, pp. 101-107, (1965)
  • [5] Campbell H.G., Dudek R.A., Smith M.L., A heuristic algorithm for the n job, m machine sequencing problem, Manag. Sci., 16, 10, (1970)
  • [6] Nawaz M., Enscore E.E., Ham I., A heuristic algorithm for the m -machine, n -job flow-shop sequencing problem, Omega, 11, 1, pp. 91-95, (1983)
  • [7] Jia H.Z., Fuh J.Y., Nee A.Y., Zhang Y.F., Web-based multi-functional scheduling system for a distributed manufacturing environment, Concurr. Eng., 10, 1, pp. 27-39, (2002)
  • [8] Jia H.Z., Fuh J.Y., Nee A.Y., Zhang Y.F., Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems, Comput. Ind. Eng., 53, 2, pp. 313-320, (2007)
  • [9] Jia H.Z., Nee A.Y., Fuh J.Y., Zhang Y.F., A modified genetic algorithm for distributed scheduling problems, J. Intell. Manuf., 14, 3-4, pp. 351-362, (2003)
  • [10] Chan F.T., Chung S.H., Chan L.Y., Finke G., Tiwari M.K., Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach, Robot. Comput. Integr. Manuf., 22, 5, pp. 493-504, (2006)
123456