Open AccessSchool of Mechanical Engineering, Shanghai Jiao Tong University, 200240, Shanghai, China
Author(s) -
Zilong Zhuang,
Zhi Yao Lu,
Zi Zhao Huang,
ChengLiang Liu,
Wei Qin
Publication year - 2019
Publication title -
mathematical biosciences and engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.451
H-Index - 45
eISSN - 1551-0018
pISSN - 1547-1063
DOI - 10.3934/mbe.2019224
Subject(s) - tree traversal , computer science , scheduling (production processes) , dynamic priority scheduling , job shop scheduling , heuristic , mathematical optimization , fair share scheduling , flow shop scheduling , two level scheduling , distributed computing , artificial intelligence , algorithm , computer network , quality of service , mathematics , routing (electronic design automation)
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.