期刊
INFORMS JOURNAL ON COMPUTING
卷 20, 期 3, 页码 333-344出版社
INFORMS
DOI: 10.1287/ijoc.1070.0246
关键词
scheduling; identical parallel machines; bin packing; scatter search; column generation
Given a set of jobs with associated processing times, and a set of identical machines, each of which can process at most one job at a time, the parallel machine scheduling problem is to assign each job to exactly one machine so as to minimize the maximum completion time of a job. The problem is strongly NP-hard and has been intensively studied since the 1960s. We present a metaheuristic and an exact algorithm and analyze their average behavior on a large set of test instances from the literature. The metaheuristic algorithm, which is based on a scatter search paradigm, computationally proves to be highly effective and capable of solving to optimality a very high percentage of the publicly available test instances. The exact algorithm, which is based on a specialized binary search and a branch-and-price scheme, was able to quickly solve to optimality all remaining instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据