An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes
An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes
复制标题
DOI：
10.1016/j.engappai.2010.01.031
复制
发表时间：
2010-09-01
影响因子：
8
通讯作者：
Jolai, Fariborz
中科院分区：
文献类型：
--
作者：
Kashan, Ali Husseinzadeh;Karimi, Behrooz;Jolai, Fariborz
本文研究了单机批处理中不同尺寸工件的排序问题。批处理机是一种可以同时处理多个工件的机器，只要被处理的工件的总大小不超过机器的能力。批处理时间等于批处理中所有作业的最长处理时间。针对最大完工时间和最大拖期双目标同时最小化问题，提出了两种基于不同表示方案的多目标遗传算法。第一种算法通过遗传算子生成工件序列进行搜索，然后将工件保持在序列中的顺序，第二种算法采用遗传算子直接生成工件批量的思想，并通过启发式过程保证可行性。在第二种算法中使用的表示类型允许引入具有使搜索偏向于每个目标的能力的启发式算法，并且还允许与局部搜索启发式算法杂交，该局部搜索启发式算法给出了找到帕累托最优或局部有效的帕累托解的能力。计算结果表明，随着问题规模的增大，后一种算法得到的非支配解在接近真实Pareto最优解和保持Pareto集多样性方面具有非常上级的优势. (C)2010爱思唯尔有限公司版权所有。
This paper addresses the problem of scheduling jobs with non-identical sizes on a single batch processing machine. A batch processing machine is one which can process multiple jobs simultaneously as a batch as long as the total size of jobs being processed does not exceed the machine capacity. The batch processing time is equal to the longest processing time among all jobs in the batch. For the simultaneous minimization of the bi-criteria of makespan and maximum tardiness, we propose two different multi-objective genetic algorithms based on different representation schemes. While the first algorithm do search via generating sequences of jobs using genetic operators and then batching jobs keeping their order in the sequence, the second algorithm uses the idea of generating batches of jobs directly using genetic operators and ensures feasibility through using heuristic procedures. The type of representation used in the second algorithm allows introducing heuristics with the ability of biasing the search towards each objective and also allows hybridization with a local search heuristic that gives the ability of finding Pareto-optimal or locally efficient Pareto-solutions. Computational results show that the non-dominated solutions obtained by the latter algorithm are very superior in closeness to the true Pareto-optimal solutions and to keep diversity in the obtained Pareto-set, as the problem size increases. (C) 2010 Elsevier Ltd. All rights reserved.