Study On Hybrid Algorithm For Multi-Shop Integrated Scheduling Problem

Integrated scheduling considers processing and assembly at the same time.Its characteristic is that production tasks can be flexibly scheduled according to the product BOM structure without waiting for the predefined process sequence.It has a high degree of flexibility and autonomy,and is suitable for the needs of less than truckload OEM and personalized customization.However,the process of personalized customized products is more complex.A wide variety of non-standard processes and temporary processes make it difficult for a single workshop to meet such a wide range of production conditions.It is necessary to cooperate with external workshops to meet this wide range of process requirements.So,the study of multi shop integrated scheduling problem(MISP)has certain theoretical significance and practical value.According to the characteristics of different multi-shop scheduling problems,the research work in this paper is divided into the following parts.1.For the MISP scheduling problem considering the actual transportation time,based on the public logistics network,a mathematical model to minimize the total tardiness is established.In order to deal with the tree constraint relationship between operations,a discrete differential updating strategy is proposed,which can make the operation encoding sequence still meet the tree constraint relationship after updating.To meet the constraints of multi-shop transportation time,a multi-shop decoding method based on first time fit strategy is proposed.To improve the solution quality,GA(genetic algorithm)based on crossing mutation strategy and ABC(artistic bee colony)based on the proposed discrete differential update strategy are mixed.The hybrid strategy of GA-ABC is that two populations evolve independently and exchange information once in each iteration.The crossing mutation strategy of GA and the discrete differential update strategy of ABC are two different types of search behavior,which is equivalent to increasing the diversity of searching behavior and helping to find better solutions.The effectiveness of the proposed hybrid algorithm is verified by the simulation experiment.The results show that compared with the single searching behavior algorithm,the proposed algorithm can search the solution with shorter total tardiness.2.For the MISP scheduling problem considering transportation capacity,a mathematical model based on virtual transportation machine and virtual transportation operation is established.A decoding method based on virtual transport machine and virtual transport operation is proposed in order to translate the operation sequences into a solution that meets the vehicle transport constraints.The main decoding strategy is to generate an initial solution while ignoring the vehicle capacity,next,calculate and merge the transportation demands of the initial solution,then,transform the transport demands into virtual transport operations on virtual transport machine,last,recalculate the operation sequence and generate a scheduling solution containing virtual transport operation according to the new operation sequence.The proposed decoding method is embedded into GA-ABC,which makes GA-ABC capable of solving MISP scheduling problems that take transport capacity into account.The correctness and effectiveness of the proposed algorithm is tested through simulation experiment,and the result show that the proposed hybrid method can effectively guarantee the product delivery time.3.For the MISP scheduling problem with non-closed linked operations,a mathematical model that considers both the non-closed link constraint and the multi-shop transport constraint is developed.In order to convert the operation sequence into a scheduling solution that satisfies both the multi-shop transport constraint and the non-closed link constraint,a delay-time-based decoding method is proposed and embedded into the GA-ABC so that the GA-ABC has the ability to handle the 2constraints.The main idea of the decoding method is that the start time of an operation is determined by the completion time of the immediately predecessors,the inter-workshop transport delay and the non-close connection delay,so by calculating these time constraints,the start time of the target operation can be determined,thus completing the decoding.The results of the simulation experiments show that the proposed hybrid method is correct and feasible and can obtain solution with shorter total tardiness than the control algorithm.4.Although a multi-shop collaborative production model can offer a very wide range of process technologies and machining capabilities to a single workshop.However,in practice,the load on external shops varies,resulting in potentially different idle periods for each shop,which can affect the efficiency of multi-shop collaboration.In this case,special optimization is required for the MISCP(Multi-shop Idle Capacity Scheduling Problem).To this end,a three-window rescheduling mechanism based on GA and B&B(Branch and Bound)is proposed to handle dynamic events.In each dynamic event time,the designed GA algorithm is used to output a pre-scheduling scheme,and the pre-scheduling scheme is divided into three parts: dispatched,ready to be dispatched and reschedulable.Then,utilizing the parallel time period when the dispatched part is executing,the B&B method is used to improve and optimize the reschedulable part.The experimental data shows that the proposed three-window rescheduling mechanism cleverly exploits the characteristics of both GA and B&B solution methods,enabling the B&B method to significantly improve the pre-scheduling scheme which generated by GA and obtain a better total tardiness than the control algorithms.Moreover,these improvements make use of the parallel time period when the dispatched part is executing production without adverse effects,making the proposed hybrid GA-B&B method suitable for practical situations such as retrofitting of old systems.