基于JIT的非等同并行多机调度问题的混合遗传算法  

Hybrid Genetic Algorithm for Solving Job Scheduling Problem on Non-identical Parallel Machines Based on JIT Technique

作　　者：黄德才[1] 郭海东[1] 

机构地区：[1]浙江工业大学信息工程学院,浙江杭州310032

出　　处：《计算机集成制造系统-CIMS》2004年第3期298-302,共5页

基　　金：浙江省自然科学基金资助项目(601076)。~~

摘　　要：针对一类NP完全问题的多目标、非等同、并行多机作业调度问题,设计了一个混合遗传算法。该算法在设计过程中针对该问题的特点,设计了一种动态适应度函数;将求解单机问题最优解的有效算法混合在编码方案中,设计了一种不包括作业顺序的简单编码方案,从而降低了算法的实现难度,并提高了执行效率。数值仿真实验表明,该算法具有收敛速度快、优化效果好等特点,适合于求解较大规模的问题。A hybrid genetic algorithm (HGA) is presented for the problem of minimizing the range of lateness and make-span on parallel non-identical machines, which is a NP-complete. There are two new method presented for the HGA. Firstly, a dynamic fitness function is introduced according to the requirement of the scheduling problem. Secondly, a simple coding method for the HGA is given. This new coding method does not include the ranking information of job list, and it embeds the optimal effective algorithm for solving the corresponding single machine problem, which makes the HGA easy programming and enhances the efficiency of the HGA. Numerical simulations illustrate that the HGA has the properties of fast convergence, and can be used to solve larger size problems.

关 键 词：作业调度 混合遗传算法 准时生产 JIT 非等同并行多机调度问题 生产管理 

分 类 号：O224[理学—运筹学与控制论] F273[理学—数学]