Research article Special Issues

A novel complex network based dynamic rule selection approach for open shop scheduling problem with release dates

  • Received: 30 March 2019 Accepted: 15 May 2019 Published: 21 May 2019
  • In the open shop scheduling problem, resources and tasks are required to be allocated in an optimized manner, but when the arrival of tasks is dynamic, the problem becomes much more difficult. To solve large scale open shop scheduling problem with release dates, heuristic algorithms are more promising compared with metaheuristic algorithms. In this paper, a framework of general scheduling object is developed, under which open shop scheduling problem is described. Then, a complex scheduling network model for open shop scheduling problem is established, and the problem is transformed into reasonably arranging the node traversal order with the goal of traversing all nodes in the network as quickly as possible, on condition that each node has a traversal time and only disconnected nodes can be traversed simultaneously. Considering that network structural features and local time attributes of nodes can provide heuristic information, six single heuristic rules are raised and a novel complex network based dynamic rule selection approach is proposed to solve dynamic open shop problem by switching dynamically the scheduling rules based on real-time production status. Finally, two experiments are carried out and the experimental results show that the proposed heuristic rules have acceptable performance, and the proposed complex network based dynamic rule selection approach is feasible.

    Citation: Zilong Zhuang, Zhiyao Lu, Zizhao Huang, Chengliang Liu, Wei Qin. A novel complex network based dynamic rule selection approach for open shop scheduling problem with release dates[J]. Mathematical Biosciences and Engineering, 2019, 16(5): 4491-4505. doi: 10.3934/mbe.2019224

    Related Papers:

  • In the open shop scheduling problem, resources and tasks are required to be allocated in an optimized manner, but when the arrival of tasks is dynamic, the problem becomes much more difficult. To solve large scale open shop scheduling problem with release dates, heuristic algorithms are more promising compared with metaheuristic algorithms. In this paper, a framework of general scheduling object is developed, under which open shop scheduling problem is described. Then, a complex scheduling network model for open shop scheduling problem is established, and the problem is transformed into reasonably arranging the node traversal order with the goal of traversing all nodes in the network as quickly as possible, on condition that each node has a traversal time and only disconnected nodes can be traversed simultaneously. Considering that network structural features and local time attributes of nodes can provide heuristic information, six single heuristic rules are raised and a novel complex network based dynamic rule selection approach is proposed to solve dynamic open shop problem by switching dynamically the scheduling rules based on real-time production status. Finally, two experiments are carried out and the experimental results show that the proposed heuristic rules have acceptable performance, and the proposed complex network based dynamic rule selection approach is feasible.


    加载中


    [1] Y. T. Leung, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Inc. 2004.
    [2] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4th ed., Boston, MA: Springer, New York, 2012.
    [3] D. Mourtzis, Internet based collaboration in the manufacturing supply chain, Cirp J. Manufact. Sci. Technol., 4 (2011), 296–304.
    [4] T. F. Gonzalez and S. Sahni, Open shop scheduling to minimize finish time, J. ACM, 23 (1976), 665–679.
    [5] D. Bai, Z. Zhang, Q. Zhang, et al., Open shop scheduling problem to minimize total weighted completion time, Eng. Optimiz., 49 (2017), 98–112.
    [6] J. Blazewicz, W. Domschke and E. Pesch, The job shop scheduling problem: Conventional and new solution techniques, Eur. J. Oper. Res., 93 (1996), 1–33.
    [7] R. L. Graham, E. L. Lawler, J. K. Lenstra, et al., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals discrete mathematics (1979), 287–326.
    [8] M. Pinedo, Scheduling: theory, algorithms, and systems. Prentice Hall, USA, 2002.
    [9] D. Bai and L. Tang, Open shop scheduling problem to minimize makespan with release dates, Appl. Math. Model., 37 (2013), 2008–2015.
    [10] E. L. Lawler, J. K. Lenstra, A. H. Kan, et al., Minimizing maximum lateness in a two-machine open shop, Math. Oper. Res., 6 (1981), 153–158.
    [11] R. Chen, W. Huang and G. Tang, Dense open-shop schedules with release times, Theor. Comput. Sci., 407 (2008), 389–399.
    [12] P. Brucker, J. L. Hurink, B. Jurisch, et al. A branch & bound algorithm for the open-shop problem, Discret Appl. Math., (1997), 43–59.
    [13] U. Dorndorf, P. Erwin and T. Phanhuy, Solving the open shop scheduling problem, J. Sched., 4 (2001), 157–174.
    [14] C. Liaw, A hybrid genetic algorithm for the open shop scheduling problem, Eur. J. Oper. Res., 124 (2000), 28–42.
    [15] F. Ahmadizar and M. H. Farahani, A novel hybrid genetic algorithm for the open shop scheduling problem, Int. J. Adv. Manuf. Technol., 62 (2012), 775–787.
    [16] X. Li, L. Gao, Q. Pan, et al., An Effective Hybrid Genetic Algorithm and Variable Neighborhood Search for Integrated Process Planning and Scheduling in a Packaging Machine Workshop, IEEE Trans. Syst. Man Cybern., (2018), 1–13.
    [17] X. Li, L. Gao, W. Wang, et al., Particle swarm optimization hybridized with genetic algorithm for uncertain integrated process planning and scheduling with interval processing time, Comput. Ind. Eng., (2019).
    [18] X. Li, S. Xiao, C. Wang, et al., Mathematical modeling and a discrete artificial bee colony algorithm for the welding shop scheduling problem, Memet. Comput., (2019), 1–19.
    [19] X. Li, C. Lu, L. Gao, et al., An Effective Multiobjective Algorithm for Energy-Efficient Scheduling in a Real-Life Welding Shop, IEEE Trans. Ind. Inform., 14 (2018), 5400–5409.
    [20] A. Barabasi and R. Albert, Emergence of Scaling in Random Networks, Science, 286 (1999), 509–512.
    [21] D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks, Nature, 393 (1998), 440–442.
    [22] Q. Xuan and T. J. Wu, Network model and heuristic scheduling rule designing method for complex open shop problems, J. Zhejiang University Eng. Sci. Edition, 45 (2011), 961–968.
    [23] Q. Xuan and T. J. Wu, Open shop complex scheduling network model and characteristic analysis, J. Zhejiang University. Eng. Sci., 45 (2011), 589–595.
    [24] X. Li, Y. Yuan, W. Sun, et al. Bottleneck identification in job-shop based on network structure characteristic, Comput. Integr. Manuf., 4 (2016), 23.
    [25] D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization, IEEE T. Evol. Comput., 1 (1997), 67–82.
    [26] A. S. Manne, On the job-shop scheduling problem, Oper. Res., 8 (1960), 219–223.
    [27] L. Lu, D. Chen, X. Ren, et al. Vital nodes identification in complex networks, Phys. Rep. Rev. Sec. Phys. Lett., 650 (2016), 1–63.
    [28] T. Bian and Y. Deng, Identifying influential nodes in complex networks: A node information dimension approach, Chaos, 28 (2018).
    [29] E. D. Taillard, Benchmarks for basic scheduling problems, Eur. J. Oper. Res., 64 (1993), 278–285.
    [30] G. C. Ciro, F. Dugardin, F. Yalaoui, et al., Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach, Int. J. Prod. Res., 54 (2016), 4854–4881.
    [31] A. Clauset, C. R. Shalizi and M. E. J. Newman, Power-law distributions in empirical data, SIAM Rev., 51 (2009), 661–703.
    [32] Y. S. Virkar, Power-Law Distributions and Binned Empirical data, Ann. Appl. Stat., 8 (2014), 89–119.
  • Reader Comments
  • © 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

Metrics

Article views(3563) PDF downloads(484) Cited by(7)

Article outline

Figures and Tables

Figures(4)  /  Tables(2)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog