A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates

作者：Tang Lixin^*; Zhang Yanyan

来源：International Journal of Systems Science, 2011, 42(7): 1133-1141.

DOI：10.1080/00207720903308389

• Lagrangian relaxation
• dissimilar parallel machine
• release dates
• dynamic programming
• machine-based decomposition
• heuristics

In this article we investigate the parallel machine scheduling problem with job release dates, focusing on the case that machines are dissimilar with each other. The goal of scheduling is to find an assignment and sequence for a set of jobs so that the total weighted completion time is minimised. This type of production environment is frequently encountered in process industry, such as chemical and steel industries, where the scheduling of jobs with different purposes is an important goal. This article formulates the problem as an integer linear programming model. Because of the dissimilarity of machines, the ordinary job-based decomposition method is no longer applicable, a novel machine-based Lagrangian relaxation algorithm is therefore proposed. Penalty terms associated with violations of coupling constraints are introduced to the objective function by Lagrangian multipliers, which are updated using subgradient optimisation method. For each machine-level subproblem after decomposition, a forward dynamic programming algorithm is designed together with the weighted shortest processing time rule to provide an optimal solution. A heuristics is developed to obtain a feasible schedule from the solution of subproblems to provide an upper bound. Numerical results show that the new approach is computationally effective to handle the addressed problem and provide high quality schedules.

• 出版日期2011
• 单位东北大学