摘要
提出了平行机作业方式和流水作业方式的综合的作业方式,属于NP难问题。应用网络理论构造了平行流水作业的非连接图模型,可实现全局随机寻优的实基因编码遗传算法求解平行流水作业计划问题。选取各种规模的10余个标准算例,以加工流程时间为目标函数进行仿真。对每个算例进行10次随机计算,所得最优值与平均值差异率小于1.8%。对于reC39等大规模问题,10次随机计算的平均花费时间少于260s。
After analyzing the practical production types, a new concept identical parallel flow shop scheduling problem （IFSP） is proposed, which is the integration of identical parallel machine scheduling and flow shop scheduling. The solving of IFSP is non-polynomial hard. A disjunctive graph is established for presenting IFSP. Genetic algorithm （GA） is used to solve IFSP. The GA employs real number to encode chromosome, which is able to search solutions in the whole field. Ten benchmark instances are chosen for the study with makespan as the objective function. Each instance is computed 10 times stochastically. The difference between the best value of makespan and its mean value of 10 times＇ computation is less than 1.8＆. For the big-scale instance such as reC39, the computation consumes less than 260 seconds averagely.
出处
《工业工程与管理》
2006年第1期58-61,共4页
Industrial Engineering and Management
基金
浙江省自然科学基金(项目Z604342
Y605421)
宁波市青年基金项目(2005A620004)
浙江省教育厅科研基金项目(20051643)
关键词
遗传算法
平行流水作业
流水作业
平行机作业
genetic algorithm
identical parallel flow shop scheduling
identical parallel machine scheduling
flow shop scheduling
