Research On Integrated Scheduling Algorithm With Components Division And Driven Matching For Two Workshops

As the development of integrated scheduling research towards to solve theproblem of more practical，research has shifted from single workshop to morecomplex distributed scheduling of more workshops. Although, at home andabroad, there have been a lot of researches about single shop scheduling anddistributed scheduling, but achievements appear less in view of the integratedscheduling.Aiming at the problem that how to effectively resolve complex products andimprove the speed of processing in two workshops with symmetrical equipmentresources, the integrated scheduling algorithm of two workshops based on ACPMis designed. In order to optimize the parallel processing of two workshops, thepre scheduling control strategy is designed, which shorten the difference ofprocessing time between two workshops; in order to control the migrationsbetween processes, the clusters of processes overall is processed; because thefork point processes influence the process migrations, and the buffering processesinfluence the start time of successor process, so the special types of processadjustment strategy is designed for these processes, both considering the situationof parallel processing and controling migrations.The high performance guarantee of the algorithm with two workshops iseffective to reduce the number of migrations. And equipment resources includesymmetry and asymmetry. For this reason, the thought of processing thecomponent as a unit is put forward for the first time, and the algorithm ofcomponents division is designed for the integrated scheduling of two workshopswith different equipment resources. In the situation of components withconnected tree structure, the algorithm makes the processes of component without repeating and contradictory process. The algorithm both considers thesymmetry and asymmetry, reduces the number of migrations more effectively,makes the partitioning of process more operable, makes the task of allocationmore reasonable, and facilitates the whole scheduling for future.Aiming at the problem that how to effectively decompose complex productsand improve the processing speed, an integrated scheduling algorithm ofcomponent matching with two different workshops driven is proposed. In order toeffectively decrease the number of process migrations, the strategy ofcomponents partitioning is designed, which divided processed into severalcorresponding components. In order to balance the load of two workshops, thestrategy of the long path component matching is proposed, which gives highpriority for the longest path component to select the workshops, and the commoncomponents should match to the workshop which scheduling process has endedearlier. In order to make full use of the free time between the scheduled processes,the strategy of idle time adapting is designed for the long path component.Examples show that the proposed algorithm not only can reduce the number ofmigrations, control the balance of the load and shorten the total time ofprocessing, but also can control the algorithm complexity in no more than threetimes polynomial.