Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities

被引：20

作者：

Jia, Zhaohong ^{[1
]}

Li, Xiaohao ^{[1
]}

Leung, Joseph Y. T. ^{[2
,3
]}

机构：

[1] Anhui Univ, Minist Educ, Key Lab Intelligent Comp & Signal Proc, Hefei 230039, Anhui, Peoples R China

[2] Hefei Univ Technol, Sch Management, Hefei 230009, Anhui, Peoples R China

[3] New Jersey Inst Technol, Dept Comp Sci, Newark, NJ 07102 USA

来源：

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2017年 / 67卷

基金：

中国国家自然科学基金;

关键词：

Scheduling; Parallel batch machines with arbitrary capacities; Release times; Makespan; Ant colony optimization; HYBRID GENETIC ALGORITHM; PROCESSING MACHINE; PARALLEL MACHINES; MAXIMUM LATENESS; MINIMIZATION; HEURISTICS;

D O I：

10.1016/j.future.2016.07.017

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of scheduling a set of arbitrary size jobs with dynamic arrival times on a set of parallel batch machines with arbitrary capacities; our goal is to minimize the makespan. We first give a mathematical model of the problem, and provide a lower bound for the objective function value. Based on different rules of batching the jobs and scheduling the batches on the machines, two meta-heuristics based on Ant Colony Optimization (ACO) are proposed to solve the problem. The performance of the proposed algorithms is evaluated and compared with existing heuristics by computational experiments. Our results show that one of the ACO algorithms consistently finds better solutions than all the others in a reasonable amount of time. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：22 / 34

页数：13

共 46 条

[1] Metaheuristics for scheduling jobs with incompatible families on parallel batching machines [J].