Research On Zero Wait Hybrid Flow Shop Scheduling Based On Improved Lagrangian Relaxation

Hybrid Flow Shop(HFS) scheduling is a complex decision-making process of production, we can extract HFS structure in glass, steel and other reality process industry. HFS scheduling problem is the promotion of general Flow Shop(FS) scheduling problem, which is characterized that at least one processing stage contains more than one identical parallel machine. In actual HFS system, dispatching often subject to machine capacity, production time and other resources. Therefore, how to scientific and reasonable allocation of various resources under the condition of existing resources is particularly important. On the basis of HFS scheduling research, This paper mainly studied the zero wait HFS scheduling with release time and zero wait HFS scheduling problem with deadline condition.For zero wait HFS scheduling problem with release time, the objective is to minimize the total weighted completion time of all jobs. The static discrete time integer programming model is established. In order to solve the problem, a Lagrangian relaxation algorithm based on surrogate subgradient method is designed. Lagrangian relaxed problem is decomposed into multiple job-level subproblems based on job decomposition strategy. Instead of subgradient method which requires optimal resolution of all subproblems at each iteration, and then approximate resolution of the relaxed problem by minimizing several subproblems so that a better Lagrangian multipliers direction is obtained. A heuristic method is then designed to construct feasible schedules due to the resulting solution is often not feasible. Computation experiments show that the developed Lagrangian relaxation is feasible and effective for zero wait HFS scheduling problem with release time, and has strong practical value to guide productionBased on the above studies, considering the deadline constraints, zero wait HFS scheduling problems with deadline condition were studied. The static discrete time integer programming model is established, still using the solution of Lagrange relaxation algorithm based on the surrogate subgradient algorithm to solve this problem. The simulation results proved that the developed Lagrangian relaxation is feasible and effective for zero wait HFS scheduling problem under real-time conditions...