Unrelated Parallel Machine Scheduling using Lagrangian Relaxation Algorithm

摘要：

In this paper, we consider the problem of scheduling n jobs on m unrelated parallel machines under the criterion of minimizing the total weighted completion time. For this well known NP-hard problem, a novel mixed integer programming model is proposed. To facilitate the design of Lagrangian relaxation algorithm, unlike classical job-based decomposition, this paper proposes a machine-based decomposition strategy to solve the problem. The original problem is relaxed and decomposed into machine-level subproblems, each of which is optimally solved by dynamic programming algorithm based on WSPT order. A computational experiment is provided for the scheduling problem with randomly generated instances. The numerical results show that the proposed Lagrangian relaxation method provides good schedules and converges fast for various sizes of problems.

关键词： Scheduling Unrelated ParallelMmachine Lagrangian Relaxation Dynamic Programming

作者: Yanyan ZHANG Lixin TANG Guofen HU

作者单位: The Logistics Institute,Northeastern University,Shenyang,China Shanghai Baosight Software Co.Ltd.,China

会议类型: 国际会议

会议名称: 工业工程与系统管理2007年国际会议(International Conference on Industrial Engineering and Systems Management)(IESM 2007)

会议地点: 北京

会议语种:英文

在线出版日期: 2007-05-30（万方平台首次上网日期，不代表论文的发表时间）