无等待排列流水车间提前/延期调度问题  

Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

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

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

出　　处：《北京邮电大学学报》2009年第6期72-76,共5页Journal of Beijing University of Posts and Telecommunications

基　　金：科技部科技型中小企业技术创新基金项目(06C26221100674)

摘　　要：在满足任务的交货期相同和工序无等待等假设条件后,提出了一种排列流水车间提前/延期惩罚调度问题的启发式算法.该算法首先按照7种任务排序的规则分别得到任务的较优次序,然后分别使用NEH算法构造优化解,再对每个不同解进行邻域搜索,最后比较得出最优解.在中小规模问题的数据实验中,该算法求解与最优解的相近程度达到99%左右,并且通过大量数据样本的标准差验证,求解的稳定性也非常好.在大规模问题的数据实验中,该启发式算法体现出非常好的优化性能,同constraint programming(ILOG-CP)优化引擎算法比较,计算结果也明显占优.Given the same due date and no idle time in processes, a heuristic algorithm for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. Firstly, the algorithm gets the relatively good sequence of the jobs according to the sorted sequence regulation of 7 jobs. And then, the NEH algorithm is used to get the optimized solutions. At last, the optimal solutions are achieved by comparing the neighborhood searching results for every solutions. 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 99 %. Meanwhile through testing the standard deviation of the large scale samples, it is shown that the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good optimized performances and its calculated results are better than those got by ILOG-constraint programming（CP） optimized engine.

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

分 类 号：TP39[自动化与计算机技术—计算机应用技术]