A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 8 Issue 6
Jun.  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
Z. Y. Zhao, S. X. Liu, M. C. Zhou, and A. Abusorrah, "Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem," IEEE/CAA J. Autom. Sinica, vol. 8, no. 6, pp. 1199-1209, Jun. 2021. doi: 10.1109/JAS.2020.1003539
Citation: Z. Y. Zhao, S. X. Liu, M. C. Zhou, and A. Abusorrah, "Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem," IEEE/CAA J. Autom. Sinica, vol. 8, no. 6, pp. 1199-1209, Jun. 2021. doi: 10.1109/JAS.2020.1003539

Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem

doi: 10.1109/JAS.2020.1003539
Funds:  This work was supported by the China Scholarship Council Scholarship, the National Key Research and Development Program of China (2017YFB0306400), the National Natural Science Foundation of China (62073069) and the Deanship of Scientific Research (DSR) at King Abdulaziz University (RG-48-135-40)
More Information
  • Group scheduling problems have attracted much attention owing to their many practical applications. This work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time, release time, and due time. It is originated from an important industrial process, i.e., wire rod and bar rolling process in steel production systems. Two objective functions, i.e., the number of late jobs and total setup time, are minimized. A mixed integer linear program is established to describe the problem. To obtain its Pareto solutions, we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods, i.e., an insertion-based local search and an iterated greedy algorithm. The computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its peers. Its high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.

     

  • loading
  • [1]
    J. S. Neufeld, J. N. D. Gupta, and U. Buscher, “A comprehensive review of flowshop group scheduling literature,” Comput. Oper. Res., vol. 70, pp. 56–74, Jun. 2016. doi: 10.1016/j.cor.2015.12.006
    [2]
    R. Zhang, S. J. Song, and C. Wu, “Robust scheduling of hot rolling production by local search enhanced ant colony optimization algorithm,” IEEE Trans. Ind. Inf., vol. 16, no. 4, pp. 2809–2819, Apr. 2020. doi: 10.1109/TII.2019.2944247
    [3]
    Z. Y. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and L. Qi, “Decomposition method for new single-machine scheduling problems from steel production systems,” IEEE Trans. Autom. Sci. Eng., vol. 17, no. 3, pp. 1376–1387, Jul. 2020.
    [4]
    Z. Y. Zhao, S. X. Liu, M. C. Zhou, D. You, and X. W. Guo, “Heuristic scheduling of batch production processes based on petri nets and iterated greedy algorithms,” IEEE Trans. Autom. Sci. Eng., to be published. 2020.
    [5]
    G. Fortino, F. Messina, D. Rosaci, G. M. L. Sarné, and C. Savaglio, “A trust-based team formation framework for mobile intelligence in smart factories,” IEEE Trans. Ind. Inf., vol. 16, no. 9, pp. 6133–6142, Sep. 2020. doi: 10.1109/TII.2020.2963910
    [6]
    Z. Y. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and J. L. Xue, “Iterated greedy algorithm for solving a new single machine scheduling problem,” in Proc. IEEE 16th Int. Conf. Networking, Sensing and Control, Banff, Canada, 2019, pp. 430–435.
    [7]
    Z. Y. Zhao, S. X. Liu, M. C. Zhou, and X. W. Guo, “Intelligent scheduling for a rolling process in steel production systems,” in Proc. IEEE Int. Conf. Networking, Sensing and Control, Nanjing, China, 2020, pp. 1–6.
    [8]
    C. Schwindt and N. Trautmann, “Batch scheduling in process industries: An application of resource-constrained project scheduling,” OR-Spektrum, vol. 22, no. 4, pp. 501–524, Nov. 2000. doi: 10.1007/s002910000042
    [9]
    J. Pei, X. B. Liu, W. J. Fan, P. M. Pardalos, and S. J. Lu, “A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers,” Omega, vol. 82, pp. 55–69, Jan. 2019. doi: 10.1016/j.omega.2017.12.003
    [10]
    E. Mehdizadeh, R. Tavakkoli-Moghaddam, and M. Yazdani, “A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times,” Appl. Math. Model., vol. 39, no. 22, pp. 6845–6859, Nov. 2015. doi: 10.1016/j.apm.2015.02.027
    [11]
    A. Allahverdi, “The third comprehensive survey on scheduling problems with setup times/costs,” Eur. J. Oper. Res., vol. 246, no. 2, pp. 345–378, Oct. 2015. doi: 10.1016/j.ejor.2015.04.004
    [12]
    C. H. Lee, C. J. Liao, and C. W. Chao, “Scheduling with multi-attribute setup times,” Comput. Ind. Eng., vol. 63, no. 2, pp. 494–502, Sep. 2012. doi: 10.1016/j.cie.2012.04.012
    [13]
    W. J. Chen, “Sequencing heuristic for scheduling jobs with dependent setups in a manufacturing system,” Int. J. Adv. Manuf. Technol., vol. 38, no. 1–2, pp. 176–184, Jul. 2008. doi: 10.1007/s00170-007-1070-4
    [14]
    T. C. E. Cheng, Y. H. Chung, S. C. Liao, and W. C. Lee, “Two-agent singe-machine scheduling with release times to minimize the total weighted completion time,” Comput. Oper. Res., vol. 40, no. 1, pp. 353–361, Jan. 2013. doi: 10.1016/j.cor.2012.07.013
    [15]
    M. C. Vélez-Gallego, J. Maya, and J. R. Montoya-Torres, “A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan,” Comput. Oper. Res., vol. 73, pp. 132–140, Sep. 2016. doi: 10.1016/j.cor.2016.04.009
    [16]
    M. O. Adamu and A. O. Adewumi, “A survey of single machine scheduling to minimize weighted number of tardy jobs,” J. Ind. Manag. Optim., vol. 10, no. 1, pp. 219–241, Jan. 2014.
    [17]
    M. Liu, S. J. Wang, C. B. Chu, and F. Chu, “An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance,” Int. J. Prod. Res., vol. 54, no. 12, pp. 3591–3602, Jun. 2016. doi: 10.1080/00207543.2015.1108535
    [18]
    Z. Y. Wang, C. M. Wei, and L. H. Sun, “Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect,” Int. J. Prod. Res., vol. 55, no. 11, pp. 3141–3148, Jan. 2017. doi: 10.1080/00207543.2016.1264642
    [19]
    H. T. Yuan, J. Bi, M. C. Zhou, Q. Liu, and A. C. Ammari, “Biobjective task scheduling for distributed green data centers,” IEEE Trans. Autom. Sci. Eng., vol. 18, no. 2, pp. 731–742, Apr. 2021. doi: 10.1109/TASE.2019.2958979
    [20]
    H. T. Yuan, H. Liu, J. Bi, and M. C. Zhou, “Revenue and energy cost-optimized biobjective task scheduling for green cloud data centers,” IEEE Trans. Autom. Sci. Eng., vol. 18, no. 2, pp. 817–830, Apr. 2021. doi: 10.1109/TASE.2020.2971512
    [21]
    X. W. Guo, S. X. Liu, M. C. Zhou, and G. D. Tian, “Dual-objective program and scatter search for the optimization of disassembly sequences subject to multiresource constraints,” IEEE Trans. Autom. Sci. Eng., vol. 15, no. 3, pp. 1091–1103, Jul. 2018. doi: 10.1109/TASE.2017.2731981
    [22]
    S. J. Wang, M. Liu, F. Chu, and C. B. Chu, “Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration,” J. Clean. Prod., vol. 137, pp. 1205–1215, Nov. 2016. doi: 10.1016/j.jclepro.2016.07.206
    [23]
    K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002. doi: 10.1109/4235.996017
    [24]
    Y. Hou, N. Q. Wu, M. C. Zhou, and Z. W. Li, “Pareto-optimization for scheduling of crude oil operations in refinery via genetic algorithm,” IEEE Trans. Syst. Man Cybern. Syst., vol. 47, no. 3, pp. 517–530, Mar. 2017. doi: 10.1109/TSMC.2015.2507161
    [25]
    Q. F. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, Dec. 2007. doi: 10.1109/TEVC.2007.892759
    [26]
    K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, Aug. 2014. doi: 10.1109/TEVC.2013.2281535
    [27]
    H. Jain and K. Deb, “An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 602–622, Aug. 2014. doi: 10.1109/TEVC.2013.2281534
    [28]
    Q. Kang, X. Y. Song, M. C. Zhou, and L. Li, “A collaborative resource allocation strategy for decomposition-based multiobjective evolutionary algorithms,” IEEE Trans. Syst. Man Cybern. Syst., vol. 49, no. 12, pp. 2416–2423, Dec. 2019. doi: 10.1109/TSMC.2018.2818175
    [29]
    E. Ahmadi, M. Zandieh, M. Farrokh, and S. M. Emami, “A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms,” Comput. Oper. Res., vol. 73, pp. 56–66, Sep. 2016. doi: 10.1016/j.cor.2016.03.009
    [30]
    Y. Y. Han, D. W. Gong, X. Y. Sun, and Q. K. Pan, “An improved NSGA-II algorithm for multi-objective lot-streaming flow shop scheduling problem,” Int. J. Prod. Res., vol. 52, no. 8, pp. 2211–2231, 2014. doi: 10.1080/00207543.2013.848492
    [31]
    X. Q. Wu and A. D. Che, “A memetic differential evolution algorithm for energy-efficient parallel machine scheduling,” Omega, vol. 82, pp. 155–165, Jan. 2019. doi: 10.1016/j.omega.2018.01.001
    [32]
    M. Villalobos-Cid, M. Dorn, R. Ligabue-Braun, and M. Inostroza-Ponta, “A memetic algorithm based on an NSGA-II scheme for phylogenetic tree inference,” IEEE Trans. Evol. Comput., vol. 23, no. 5, pp. 776–787, Oct. 2019. doi: 10.1109/TEVC.2018.2883888
    [33]
    H. F. Wang, Y. P. Fu, M. Huang, G. Q. Huang, and J. W. Wang, “A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem,” Comput. Ind. Eng., vol. 113, pp. 185–194, Nov. 2017. doi: 10.1016/j.cie.2017.09.009
    [34]
    W. J. Fan, J. Pei, X. B. Liu, P. M. Pardalos, and M. Kong, “Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning,” J. Global Optim., vol. 71, no. 1, pp. 147–163, May 2018. doi: 10.1007/s10898-017-0536-7
    [35]
    J. Pei, B. Cheng, X. Liu, P. M. Pardalos, and M. Kong, “Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time,” Ann. Oper. Res., vol. 272, no. 1-2, pp. 217–241, Jan. 2019. doi: 10.1007/s10479-017-2481-8
    [36]
    P. Szota, S. Mróz, H. Dyja, and A. Kawałek, “3D FEM modelling and experimental verification of the rolls wear during the bar rolling process,” in Proc. Mater. Sci. Forum, vol. 706–709, pp. 1533–1538, Jan. 2012.
    [37]
    R. Ruiz and T. Stützle, “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., vol. 177, no. 3, pp. 2033–2049, Mar. 2007. doi: 10.1016/j.ejor.2005.12.009
    [38]
    A. Hussain, Y. S. Muhammad, M. N. Sajid, I. Hussain, A. M. Shoukry, and S. Gani, “Genetic algorithm for traveling salesman problem with modified cycle crossover operator,” Comput. Intell. Neurosci., vol. 2017, Article No. 7430125, 2017.
    [39]
    E. Vallada, F. Villa, and L. Fanjul-Peyro, “Enriched metaheuristics for the resource constrained unrelated parallel machine scheduling problem,” Comput. Oper. Res., vol. 111, pp. 415–424, Nov. 2019. doi: 10.1016/j.cor.2019.07.016
    [40]
    R. Ruiz, Q. K. Pan, and B. Naderi, “Iterated Greedy methods for the distributed permutation flowshop scheduling problem,” Omega, vol. 83, pp. 213–222, Mar. 2019. doi: 10.1016/j.omega.2018.03.004
    [41]
    R. Ruiz and T. Stützle, “An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives,” Eur. J. Oper. Res., vol. 187, no. 3, pp. 1143–1159, Jun. 2008. doi: 10.1016/j.ejor.2006.07.029
    [42]
    E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, “Performance assessment of multiobjective optimizers: An analysis and review,” IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 117–132, Apr. 2003. doi: 10.1109/TEVC.2003.810758
    [43]
    Y. P. Fu, M. C. Zhou, X. W. Guo, and L. Qi, “Scheduling dual-objective stochastic hybrid flow shop with deteriorating jobs via bi-population evolutionary algorithm,” IEEE Trans. Syst. Man Cybern. Syst., vol. 50, no. 12, pp. 5037–5048, Dec. 2020. doi: 10.1109/TSMC.2019.2907575
    [44]
    X. W. Guo, M. C. Zhou, S. X. Liu, and L. Qi, “Multiresource-constrained selective disassembly with maximal profit and minimal energy consumption,” IEEE Trans. Autom. Sci. Eng., vol. 18, no. 2, pp. 804–816, Apr. 2021. doi: 10.1109/TASE.2020.2992220
    [45]
    F. Yue, S. J. Song, Y. L. Zhang, J. N. D. Gupta, and R. Chiong, “Robust single machine scheduling with uncertain release times for minimising the maximum waiting time,” Int. J. Prod. Res., vol. 56, no. 16, pp. 5576–5592, May 2018. doi: 10.1080/00207543.2018.1463473
    [46]
    K. Z. Gao, F. J. Yang, M. C. Zhou, Q. K. Pan, and P. N. Suganthan, “Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm,” IEEE Trans. Cybern., vol. 49, no. 5, pp. 1944–1955, May 2019. doi: 10.1109/TCYB.2018.2817240
    [47]
    Y. M. Wang, X. P. Li, R. Ruiz, and S. C. Sui, “An iterated greedy heuristic for mixed no-wait flowshop problems,” IEEE Trans. Cybern., vol. 48, no. 5, pp. 1553–1566, May 2018. doi: 10.1109/TCYB.2017.2707067
    [48]
    X. W. Guo, S. X. Liu, M. C. Zhou, and G. D. Tian, “Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and Petri nets,” IEEE Trans. Cybern., vol. 46, no. 11, pp. 2435–2446, Nov. 2016. doi: 10.1109/TCYB.2015.2478486
    [49]
    G. Tian, Y. Ren, Y. Feng, M. Zhou, H. Zhang, and J. Tan, “Modeling and planning for dual-objective selective disassembly using and/or graph and discrete artificial bee colony,” IEEE Trans. Industrial Informatics, vol. 15, no. 4, pp. 2456–2468, Apr. 2019.
    [50]
    M. Chen, M. C. Zhou, X. W. Guo, X. S. Lu, J. C. Ji, and Z. Y. Zhao, “Grey wolf optimizer adapted for disassembly sequencing problems,” in Proc. IEEE 16th Int. Conf. Networking, Sensing and Control, Banff, Canada, 2019, pp. 46–51.
    [51]
    X. W. Guo, M. C. Zhou, S. X. Liu, and L. Qi, “Lexicographic multiobjective scatter search for the optimization of sequence-dependent selective disassembly subject to multiresource constraints,” IEEE Trans. Cybern., vol. 50, no. 7, pp. 3307–3317, Jul. 2020. doi: 10.1109/TCYB.2019.2901834
    [52]
    W. Luo, M. C. Zhou, X. W. Guo, H. P. Wei, L. Qi, and Z. Y. Zhao, “Improved artificial bee colony algorithm for solving a single-objective sequence-dependent disassembly line balancing problem,” in Proc. IEEE Int. Conf. Networking, Sensing and Control, Nanjing, China, 2020, pp. 1–6.
    [53]
    F. J. Yang, K. Z. Gao, I. W. Simon, Y. T. Zhu, and R. Su, “Decomposition methods for manufacturing system scheduling: A survey,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 2, pp. 389–400, Mar. 2018. doi: 10.1109/JAS.2017.7510805
    [54]
    J. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and L. Qi, “Modified cuckoo search algorithm to solve economic power dispatch optimization problems,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 794–806, Jul. 2018. doi: 10.1109/JAS.2018.7511138
    [55]
    K. Z. Gao, Z. G. Cao, L. Zhang, Z. H. Chen, Y. Y. Han, and Q. K. Pan, “A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 904–916, Jul. 2019. doi: 10.1109/JAS.2019.1911540
    [56]
    Q. H. Zhu, Y. Qiao, and N. Q. Wu, “Optimal integrated schedule of entire process of dual-blade multi-cluster tools from start-up to close-down,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 553–565, Mar. 2019. doi: 10.1109/JAS.2019.1911411
    [57]
    F. J. Yang, N. Q. Wu, Y. Qiao, and R. Su, “Polynomial approach to optimal one-wafer cyclic scheduling of treelike hybrid multi-cluster tools via petri nets,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 270–280, Jan. 2018. doi: 10.1109/JAS.2017.7510772
    [58]
    J. Li, X. H. Meng, and X. Dai, “Collision-free scheduling of multi-bridge machining systems: A colored traveling salesman problem-based approach,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 139–147, Jan. 2018. doi: 10.1109/JAS.2017.7510415
    [59]
    J. Q. Li, H. Y. Sang, Q. K. Pan, P. Y. Duan, and K. Z. Gao, “Solving multi-area environmental/ economic dispatch by pareto-based chemical-reaction optimization algorithm,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 5, pp. 1240–1250, Sep. 2019. doi: 10.1109/JAS.2017.7510454
    [60]
    W. Q. Xiong, C. R. Pan, Y. Qiao, N. Q. Wu, M. X. Chen, and P. Hsieh, “Reducing wafer delay time by robot idle time regulation for single-arm cluster tools,” IEEE Trans. Autom. Sci. Eng., 2020.
    [61]
    H. Yuan, J. Bi, W. Tan, M. Zhou, B. H. Li, and J. Li, “TTSA: An Effective Scheduling Approach for Delay Bounded Tasks in Hybrid Clouds,” IEEE Trans. Cybernetics, vol. 47, no. 11, pp. 3658–3668, November 2017.
    [62]
    J. Bi, H. Yuan, W. Tan, M. Zhou, Y. Fan, J. Zhang, and J. Li, “Application-Aware Dynamic Fine Grained Resource Provisioning for a Virtualized Cloud Data Center,” IEEE Trans. Autom. Science and Engineering, vlo. 14, no. 2, pp. 1172–1183, Apr. 2017.
    [63]
    H. Yuan, J. Bi and M. Zhou, “Spatial Task Scheduling for Cost Minimization in Distributed Green Cloud Data Centers,” IEEE Trans Autom. Science and Engineering, vol. 16, no. 2, pp. 729–740, April 2019.
    [64]
    Y. Fu, M. Zhou, X. Guo and L. Qi, “Scheduling Dual-Objective Stochastic Hybrid Flow Shop With Deteriorating Jobs via Bi-Population Evolutionary Algorithm,” IEEE Trans Systems, Man, and Cybernetics: Systems, vol. 50, no. 12, pp. 5037–5048, Dec. 2020.
    [65]
    Z. Cao, C. Lin, M. Zhou, and R. Huang, “Scheduling Semiconductor Testing Facility by Using Cuckoo Search Algorithm with Reinforcement Learning and Surrogate Modeling,” IEEE Trans. Autom. Science and Engineering, vol. 16, no.22, pp. 825–837, Apr. 2019.
    [66]
    P. Zhang and M. Zhou, “Dynamic Cloud Task Scheduling Based on a Two-Stage Strategy,” IEEE Trans. Autom. Science and Engineering, vol. 15, no. 2, pp. 772–783, Apr. 2018.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(7)  / Tables(7)

    Article Metrics

    Article views (1119) PDF downloads(59) Cited by()

    Highlights

    • This work tackles a new bi-objective group scheduling problem arising from a real-world steel production system.
    • It optimizes two objectives, i.e., minimizing the number of late jobs and minimizing total setup time.
    • It considers the constraints of release time, due time, and sequence-dependent setup time.
    • This work establishes a mixed-integer linear program to describe the concerned problem in a rigorous way.
    • By integrating a nondominated sorting genetic algorithm II (NSGA-II) and iterated greedy algorithm (IGA)-based local search operators, this work designs a multi-objective memetic algorithm to solve the scheduling problem well.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return