logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 7: 070202(2019) https://doi.org/10.1007/s11432-018-9693-2

A multi-objective pigeon inspired optimization algorithm for fuzzy production scheduling problem considering mould maintenance

More info
  • ReceivedAug 6, 2018
  • AcceptedNov 30, 2018
  • PublishedMay 9, 2019

Abstract

The fuzzy production scheduling problem considering mould maintenance (FPSP-MM) is studied. The processing time and the maintenance time are represented by triangular fuzzy numbers. When tasks are executed based on the sequence provided by the fuzzy schedule, the real duration of each task needs to be known so the posteriori solution with deterministic processing times can be obtained. Therefore, the concept of the schedule robustness needs to be considered for the fuzzy problem. The robustness is considered as the optimization objective except for the fuzzy makespan in this research. To optimize these two objective functions, a multi-objective pigeon inspired optimization (MOPIO) algorithm is developed. To extend the pigeon inspired optimization (PIO) algorithm from the single-objective case to the multi-objective case, non-dominated solutions are used as candidates for the leader pigeon designation and a special crowding distance is used to ensure a good distribution of solutions in both the objective space and the corresponding decision space. Furthermore, an index-based ring topology is used to manage the convergence speed. Numerical experiments on a variety of simulated scenarios show the excellent efficiency and effectiveness of the proposed MOPIO algorithm by comparing it with other algorithms.


Acknowledgment

This work was supported by Research Grants Council of the Hong Kong Special Administrative Region, China (Grant No. PolyU 15201414), National Natural Science Foundation of China (Grant Nos. 71471158, 71571120, 71271140), Research Committee of the Hong Kong Polytechnic University under Student Account Code RUKH, Project Supported by Guangdong Province Higher Vocational Colleges and Schools Pearl River Scholar Funded Scheme 2016, and Project of Innovation and Entrepreneurship Education Research Center for University Student of Guangdong Province (Grant No. 2018A073825).


References

[1] Rajkumar M, Asokan P, Vamsikrishna V. A GRASP algorithm for flexible job-shop scheduling with maintenance constraints. Int J Production Res, 2010, 48: 6821-6836 CrossRef Google Scholar

[2] Berrichi A, Yalaoui F, Amodeo L. Bi-Objective Ant Colony Optimization approach to optimize production and maintenance scheduling. Comput Operations Res, 2010, 37: 1584-1596 CrossRef Google Scholar

[3] Wong C S, Chan F T S, Chung S H. A genetic algorithm approach for production scheduling with mould maintenance consideration. Int J Production Res, 2012, 50: 5683-5697 CrossRef Google Scholar

[4] Wong C S, Chan F T S, Chung S H. A joint production scheduling approach considering multiple resources and preventive maintenance tasks. Int J Production Res, 2013, 51: 883-896 CrossRef Google Scholar

[5] Wong C S, Chan F T S, Chung S H. Decision-making on multi-mould maintenance in production scheduling. Int J Production Res, 2014, 52: 5640-5655 CrossRef Google Scholar

[6] Wang S, Liu M. Multi-objective optimization of parallel machine scheduling integrated with multi-resources preventive maintenance planning. J Manufacturing Syst, 2015, 37: 182-192 CrossRef Google Scholar

[7] Shen L, Yang H B, Gao S, et al. Production scheduling with mould maintenance in flow shop. In: Proceedings of the 4th International Conference on Sensors, Mechatronics and Automation, Zhuhai, 2016. 730--733. Google Scholar

[8] Sakawa M, Mori T. An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate. Comput Industrial Eng, 1999, 36: 325-341 CrossRef Google Scholar

[9] Arik O A, Toksari M D. Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects. Int J Production Res, 2018, 56: 2488-2505 CrossRef Google Scholar

[10] Jamrus T, Chien C F, Gen M. Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE Trans Semicond Manufact, 2018, 31: 32-41 CrossRef Google Scholar

[11] José Palacios J, González-Rodríguez I, Vela C R. Robust multiobjective optimisation for fuzzy job shop problems. Appl Soft Computing, 2017, 56: 604-616 CrossRef Google Scholar

[12] Xiong J, Xing L, Chen Y. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. Int J Production Economics, 2013, 141: 112-126 CrossRef Google Scholar

[13] Duan H, Qiao P. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int Jnl Intel Comp Cyber, 2014, 7: 24-37 CrossRef Google Scholar

[14] Li C, Duan H. Target detection approach for UAVs via improved Pigeon-inspired Optimization and Edge Potential Function. Aerospace Sci Tech, 2014, 39: 352-360 CrossRef Google Scholar

[15] Zhang B, Duan H. Three-Dimensional Path Planning for Uninhabited Combat Aerial Vehicle Based on Predator-Prey Pigeon-Inspired Optimization in Dynamic Environment.. IEEE/ACM Trans Comput Biol Bioinf, 2017, 14: 97-107 CrossRef PubMed Google Scholar

[16] Duan H, Wang X. Echo State Networks With Orthogonal Pigeon-Inspired Optimization for Image Restoration.. IEEE Trans Neural Netw Learning Syst, 2016, 27: 2413-2425 CrossRef PubMed Google Scholar

[17] Deng Y, Duan H. Control parameter design for automatic carrier landing system via pigeon-inspired optimization. NOnlinear Dyn, 2016, 85: 97-106 CrossRef Google Scholar

[18] Zhang S, Duan H. Gaussian pigeon-inspired optimization approach to orbital spacecraft formation reconfiguration. Chin J Aeronautics, 2015, 28: 200-205 CrossRef Google Scholar

[19] Qiu H X, Duan H B. Multi-objective pigeon-inspired optimization for brushless direct current motor parameter design. Sci China Technol Sci, 2015, 58: 1915-1923 CrossRef Google Scholar

[20] Qiu H, Duan H. A multi-objective pigeon-inspired optimization approach to UAV distributed flocking among obstacles. Inf Sci, 2018, doi: 10.1016/j.ins.2018.06.061. Google Scholar

[21] Fortemps P. Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Trans Fuzzy Syst, 1997, 5: 557-569 CrossRef Google Scholar

[22] Bean J C. Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA J Computing, 1994, 6: 154-160 CrossRef Google Scholar

[23] Tasgetiren M F, Liang Y C, Sevkli M. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Operational Res, 2007, 177: 1930-1947 CrossRef Google Scholar

[24] Yue C, Qu B, Liang J. A Multiobjective Particle Swarm Optimizer Using Ring Topology for Solving Multimodal Multiobjective Problems. IEEE Trans Evol Computat, 2018, 22: 805-817 CrossRef Google Scholar

[25] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Computat, 2002, 6: 182-197 CrossRef Google Scholar

[26] Lei D. Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search. Int J Adv Manuf Technol, 2011, 54: 1121-1128 CrossRef Google Scholar

[27] Coello C A C, Pulido G T, Lechuga M S. Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Computat, 2004, 8: 256-279 CrossRef Google Scholar

[28] Zitzler E, Thiele L, Laumanns M. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Computat, 2003, 7: 117-132 CrossRef Google Scholar

[29] Li J, Pan Q, Mao K. Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm. Knowledge-Based Syst, 2014, 72: 28-36 CrossRef Google Scholar

  • Figure 1

    Encoding and decoding of the example pigeon.

  • Figure 2

    (Color online) Fuzzy machine scheduling of the example pigeon.

  • Figure 3

    (Color online) Fuzzy mould scheduling of the example pigeon.

  • Figure 4

    (Color online) Machine scheduling of the example pigeon without fuzziness.

  • Figure 5

    (Color online) Mould scheduling of the example pigeon without the fuzziness.

  • Figure 6

    Flowchart of the MOPIO.

  • Figure 7

    (Color online) Factor level trend.

  • Figure 8

    (Color online) Pareto fronts of the fuzzed benchmark ($30~\times~3~\times~5$).

  • Figure 9

    (Color online) Pareto fronts of the fuzzed benchmark ($40~\times~6~\times~10$).

  • Figure 10

    (Color online) Pareto fronts of the fuzzed benchmark ($60~\times~9~\times~15$).

  • Figure 11

    (Color online) The machine scheduling for the instance $20~\times~2~\times~4$.

  • Figure 12

    (Color online) The mould scheduling for the instance $20~\times~2~\times~4$.

  • Table 1   Maintenance time based on machine/mould age
    Machine age Maintenance time Mould age Maintenance time
    $0<a^{3}\leq~180$ (150, 150, 150) $0<b^{3}\leq~120$ (150, 150, 150)
    $180<a^{3}\leq~420$ (94, 94, 94)+$(a^{1},a^{2},a^{3})/3$ $120<b^{3}\leq~280$ (94, 94, 94)+$(b^{1},b^{2},b^{3})/2$
    $420<a^{3}\leq~600$ (160, 160, 160)+$(a^{1},a^{2},a^{3})/3$ $280<b^{3}\leq~400$ (160, 160, 160)+$(b^{1},b^{2},b^{3})/2$
    $600<a^{3}$ (720, 720, 720) $400<b^{3}$ (720, 720, 720)
  • Table 2   Levels of different parameters
    Level Swarm size Max iteration of each operation $R$
    1 20 100 0.01
    2 50 200 0.2
    3 80 400 0.4
  • Table 3   Different parameters combinations and its influence on results
    No. Swarm size Max iteration of each operation $R$ ${\rm~Avg}({\rm~HV})$ ${\rm~Sd}({\rm~HV})$
    1 1 1 1 184570 25677
    2 1 2 2 183710 52467
    3 1 3 3 224810 95112
    4 2 1 2 244600 34749
    5 2 2 3 240460 54875
    6 2 3 1 304520 34394
    7 3 1 3 237050 42451
    8 3 2 1 264770 24049
    9 3 3 2 262280 15366
  • Table 4   HV comparison results of the fuzzed benchmarks
    MOPIO NSGA-II MOPSO
    $30~\times~3~\times~5$ Avg(HV) 410140 369320 394800
    Sd(HV) 35771 38432 34513
    $40~\times~6~\times~10$ Avg(HV) 296680 227000 340670
    Sd(HV) 33643 36029 42257
    $60~\times~9~\times~15$ Avg(HV) 260000 198240 225760
    Sd(HV) 66773 60707 45271
  • Table 5   CR comparison results of the fuzzed benchmarks
    MOPIO vs. NSGA-II NSGA-II vs. MOPIO MOPIO vs. MOPSO MOPSO vs. MOPIO
    $30~\times~3~\times~5$ Avg(CR) 0.7019 0.3904 0.7762 0.6362
    Sd(CR) 0.3260 0.2850 0.3016 0.2784
    $40~\times~6~\times~10$ Avg(CR) 0.5584 0.4338 0.5456 0.5219
    Sd(CR) 0.2912 0.2627 0.2530 0.3083
    $60~\times~9~\times~15$ Avg(CR) 0.5519 0.4986 0.71 0.5342
    Sd(CR) 0.334 0.3163 0.2967 0.34
  • Table 6   HV comparison results of the random benchmarks
    MOPIO NSGA-II MOPSO
    $20~\times~2~\times~4$ Avg(HV) 370120 259960 420310
    Sd(HV) 42687 52709 44402
    $35~\times~4~\times~6$ Avg(HV) 257290 115370 117340
    Sd(HV) 15086 26714 23554
    $65~\times~8~\times~10$ Avg(HV) 357070 210300 337900
    Sd(HV) 24190 38107 36947
  • Table 7   CR comparison results of the random benchmarks
    MOPIO vs. NSGA-II NSGA-II vs. MOPIO MOPIO vs. MOPSO MOPSO vs. MOPIO
    $20~\times~2~\times~4$ Avg(CR) 0.6842 0.4734 0.7957 0.7018
    Sd(CR) 0.3189 0.2486 0.1846 0.2225
    $35~\times~4~\times~6$ Avg(CR) 0.8664 0.2704 0.5145 0.5269
    Sd(CR) 0.1158 0.2374 0.4783 0.4566
    $65~\times~8~\times~10$ Avg(CR) 0.7290 0.3524 0.5578 0.5319
    Sd(CR) 0.3821 0.3453 0.3433 0.3339
  • Table 8   HV comparison results of MOPIO and MOPIO-GBA
    MOPIO MOPIO-GBA
    $20~\times~2~\times~4$ Avg(HV) 370120 174130
    Sd(HV) 42687 11377
    $30~\times~3~\times~5$ Avg(HV) 410140 160680
    Sd(HV) 35771 11802
    $35~\times~4~\times~6$ Avg(HV) 257290 126860
    Sd(HV) 42687 59960
    $40~\times~6~\times~10$ Avg(HV) 296680 157030
    Sd(HV) 33643 48312
    $60~\times~9~\times~15$ Avg(HV) 260000 103150
    Sd(HV) 66773 51170
    $65~\times~8~\times~10$ Avg(HV) 357070 276271
    Sd(HV) 24190 25374
  • Table 9   CR comparison results of MOPIO and MOPIO-GBA
    MOPIO vs. MOPIO-GBA MOPIO-GBA vs. MOPIO
    $20~\times~2~\times~4$ Avg(CR) 0.6571 0.3122
    Sd(CR) 0.4645 0.1836
    $30~\times~3~\times~5$ Avg(CR) 0.3667 0.0989
    Sd(CR) 0.5507 0.1713
    $35~\times~4~\times~6$ Avg(CR) 0.3490 0.1724
    Sd(CR) 0.5643 0.2529
    $40~\times~6~\times~10$ Avg(CR) 0.4713 0.4111
    Sd(CR) 0.4417 0.4070
    $60~\times~9~\times~15$ Avg(CR) 0.5360 0.4029
    Sd(CR) 0.3725 0.3071
    $65~\times~8~\times~10$ Avg(CR) 0.8996 0.3242
    Sd(CR) 0.1273 0.0963
  • Table 10   The unit fuzzy processing time of different moulds for instance $20~\times~2~\times~4$
    Machine 1 Machine 2
    Mould 1 (43 45 53) (43 45 53)
    Mould 2 (0 0 0) (29 33 37)
    Mould 3 (0 0 0) (45 48 57)
    Mould 4 (33 38 46) (33 38 46)

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1