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

Zilong Zhuang; Zhiyao Lu; Zizhao Huang; Chengliang Liu; Wei Qin; Zilong Zhuang; Zhiyao Lu; Zizhao Huang; Chengliang Liu; Wei Qin

doi:10.3934/mbe.2019224

Mathematical Biosciences and Engineering

2019, Volume 16, Issue 5: 4491-4505. doi: 10.3934/mbe.2019224

Previous Article Next Article

Research article Special Issues

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

School of Mechanical Engineering, Shanghai Jiao Tong University, 200240, Shanghai, China

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.
- complex network,
- open shop,
- heuristic rule,
- node traversal order,
- dynamic rule selection
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:

Abstract

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.

References

[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

Your name:*

Email:*
© 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)