Research On Hybrid Flowshop Problem With Unrelated Parallel Machines Under The Limited Conditions Of Buffer Capacity

In the context of a highly competitive global environment,the problem of production scheduling is getting more and more attention from experts.In essence,the problem of production scheduling is the process of goal optimization.Hybrid Flowshop Problem(HFP)is a more common production scheduling problem,which is generated based on the petrochemical background and widely exists in chemical,steel,pharmaceutical and other manufacturing workshops.At the same time,HFP has been proved to be an NP-hard problem.It is difficult to obtain a satisfactory solution using traditional methods,especially for more complex HFP,which may not be solved at all.Therefore,the research on HFP has certain significance in both practical production and academic theory.From the perspective of the intermediate storage strategy,the research of HFP can be divided into four categories: infinite intermediate storage,limited intermediate storage(finite buffering),no intermediate buffering(blocking),and no wait.Traditional HFP generally assumes unlimited buffer capacity between adjacent phases.However,due to production process and equipment limitations,the intermediate buffer capacity is usually limited.Therefore,this paper focuses on the research of HFP with unrelated parallel machines for the limited buffer capacity.This includes the following:(1)Aiming at HFP with finite buffer and unrelated parallel machines,a hybrid heuristic based on genetic algorithm and tabu search(HH-GA&TS)was proposed to solve the problem of minimizing completion time.In the algorithm,a twodimensional matrix coding scheme based on multi-stage parallel processing is designed,and a parameter adaptive strategy,three neighborhood rules,and tabu search are introduced.Finally,simulation experiments prove that the proposed algorithm has better solution effect compared with improved GA with NEH heuristic(NEH-IGA),GA and TS.(2)Aiming at HFP with no wait and unrelated parallel machines,a Hybrid Genetic Simulated Annealing(HGSA)algorithm is proposed to solve the problem of minimizing the total flowtime.The HGSA algorithm uses an improved NEH rule to generate the initial population and an insertion-translation approach are employed for decoding in order to meet no-wait constraints,and multiple neighborhood structures and SA are introduced to further improve the diversity of solutions.Finally,simulation experiments were conducted to test examples of different scale problems,and compare HGSA with with several heuristic algorithms proposed in the literature.The results show that the proposed algorithm has better solution quality than several other algorithms.(3)In the previous HFP studies with blocking and unrelated parallel machines,most of them discussed the completion time and rarely considered the coordination between production and transportation.However,in actual production,transportation needs to be considered independently of production.Therefore,for HFP with blocking and unrelated parallel machines,this paper considers the Transportation times and release times,an effective genetic algorithm with local search(EGA&LS)is proposed to solve the goal of minimizing the total weighted completion time.Simulation experiments compare with EGA&LS,improved adaptive GA(IAGA),NEH-IGA,the test results show that the proposed algorithm has better solution quality and is suitable for solving large-scale problems.