Chinese Journal of Computers   Full Text
Title	Dynamic Job-Shop Scheduling Algorithm with Dynamic Set of Operation Having Priority
Authors	XIE Zhi-Qiang1) YANG Jing2) YANG Guang1) TAN Guang-Yu3)
Address	1)(School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080) 2)(School of Computer Science and Technology, Harbin Engineering University, Harbin 150001) 3)(School of Mechanical Power Engineering, Harbin University of Science and Technology, Harbin 150080)
Year	2008
Issue	No.3(502—508)
Abstract &   Background	Abstract To make the total processing time of job added into job set at different time as short as possible, subject to the constraint, a new algorithm is proposed: A virtual manufacturing tree is constructed according to dynamic job set, where leaf nodes denote the operations to process firstly, root nodes denote the operations to process last and edges denote the partial relation, that is constraint between operations; the priority of operations is set according to level of operation in the virtual manufacturing tree and is regarded as a factor considered to schedule operations; A strategy of keeping machine busy is adopted to make machine try its best to process operations continually except that operations need be modified dynamically. Standby operation set is generated dynamically according to the virtual manufacturing tree, and operations in the standby operation set, subject to the priority, are scheduled with Short-time strategy, Long-path strategy and Dynamic-adjustment strategy until the set is empty, that is all operations unscheduled are finished. The example shows that the algorithm proposed can obtain favorable result for dynamic Job-Shop scheduling problem. keywords Job-Shop; virtual manufacturing tree; priority; standby operation set; dynamic adjustment background According to statistic, the cost about processing procedure of product, comparing with the total cost of product, is more than 40 percent in the manufacturing. So it is necessary to optimize the processing procedure of product, it can not only improve production efficiency and reduce cost, but also make corporation arrange production effectively and quickly and avoid risk for corporation. And it is also according with the fact that country advocates to develop the manufacturing greatly. Now the optimization of job set with non-constraint is studied mainly in abroad, but our focus is the optimization of job set with constraint. This kind of problem is based on the idea to decompose manufacturing tree of job proposed by myself, and to realize dynamic optimization procedure of job set with constraint by constructing virtual manufacturing tree and confirm the priority of operations. This study is supported by the National Natural Science Foundation of China(No.50575062), the Natural Science Foundation of Heilongjiang Province(No.F0309,F200608), Scientific Research Fund of Heilongjiang Provincial Education Department(No.10551z0008), the Key Project of Science and Technology of Harbin(No.2005AA1CG061-11) and the Key Project of Scientific Research Subsidy of Abroad Scholars of Heilongjiang Provincial Education Department(No.1152hq08). This study was started in 2003, the corresponding content about 15 papers are published by Journal of Computer Research and Development, Computer Integrated Manufacturing Systems, Chinese Journal of Mechanical Engineering and so on and international conference organized by IEEE and IET, and 4 papers of them have been accepted by EI.