排列流水车间提前/延期惩罚调度问题的启发式算法  

A Heuristic Algorithm for the Earliness and Tardiness Penalties SchedulingProblem in Permutation Flow Shop

作　　者：宁维巍[1] 闫光荣[1] 仲华惟[1] 雷毅[1] 

机构地区：[1]北京航空航天大学机械工程及自动化学院,北京100191

出　　处：《组合机床与自动化加工技术》2009年第10期102-106,112,共6页Modular Machine Tool & Automatic Manufacturing Technique

摘　　要：在满足了工序中间无储存能力、每一个任务必须连续加工和任务的交货期相同等假设条件后,提出了一种排列流水车间提前/延期惩罚调度问题的启发式算法。该算法首先按照任务的延期惩罚系数与任务加工时间的比值升序排序,得到较优次序,然后使用NEH算法寻找优化解,最后再进行邻域搜索进一步优化解决方案。在中小规模问题的数据实验中,该算法求解与最优解的相近程度达到97%以上,并且通过大量数据样本的标准差验证,求解的稳定性也非常好。在大规模问题的数据实验中,该启发式算法体现出非常好的优化性能,优化结果明显好于其他的启发式算法,并且算法在大规模问题中的运算时间也较短,在大规模的调度应用中可以代替精确的数学算法。Given no intermediate storage, no idle time in processes and common due date, a heuristic algorithm, for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. First, it sorts the jobs according to the ratio of tardiness penalties and processing time of the job by ascending sequence and gets a sorted sequence. Based on it, we use NEH algorithm to re-order the sequence and optimize the entire solution. At last, we use neighborhood search method to get a better solution. In the middle scale and small scale problems, the extent of similarity between the solutions got by the heuristic algorithm and the optimal solutions is 97 per cent. M eanwhile the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good performances, and the results got by the heuristic algorithm are better than other ones. The time of calculation of the heuristic algorithm is acceptable, so the heuristic algorithm can substitute the exact algorithm in large scale scheduling problems.

关 键 词：排列流水车间 提前延期惩罚 调度算法 

分 类 号：TH16[机械工程—机械制造及自动化] TG65[金属学及工艺—金属切削加工及机床]