Research on Optimization of Zero-wait Hybrid Flowshop Problem

Zero-wait hybrid flowshop scheduling problem is studied considering practical production characteristic of job dynamic arrival.The problem is formulated as an integer programming model to minimize the objective of total weighted completion time.A Lagrangian relaxation algorithm based on surrogate subgradient method is then designed to solve the problem.Based on job decomposition strategy,Lagrangian relaxed problem is decomposed into multiple job-level subproblems.Instead of subgradient method which requires optimal resolution of all subproblems at each iteration,the designed surrogate subgradient method requires approximate resolution of the relaxed problem by minimizing several subproblems,so that a surrogate subgradient direction is obtained to search Lagrangian multipliers.A heuristic method is then designed to construct feasible schedules.Computation experiments show that the developed Lagrangian relaxation is superior to the one using subgradient method in aspect of solution quality and convergence.