Job-Shop调度问题的分批和最优化策略  

Lot Splitting and Optimization Strategy for Job-Shop Scheduling

作　　者：陈进 王荣 

机构地区：[1]江南大学机械工程学院,无锡214122

出　　处：《机械工程学报》2010年第21期165-171,共7页Journal of Mechanical Engineering

摘　　要：缩短Job-Shop生产的工期除了用优化调度方法外,还可以对批量进行适当的分割,进一步优化生产计划。论述一种简化的Job-Shop批量分割的优化调度的方法,解决分批调度的原则、位置和对工期影响等问题,提出分批的步骤和方法。根据工艺路线的约束,用状态变量描述调度过程,在此基础上用一种启发式的算法进行通常的优化调度,在此调度计划中用一种算法找出工期最长的关键路径。分批应遵循3个规则:①分批的步骤是先优化后分批;②分批应该在这样的一个设备上,即该设备—任务完成后其加工路线上的下一个设备应该有空闲时间;③该任务工序及其后续工序至少有一个位于关键线路上。将任务—工序的等待空闲时间和回溯等待时间与当前工序和后续工序的工时等分后的可能节约工期比较,决定此处是否可以分批及其分批的大小。分批和优化达到了目标——最长工期最小。To shorten makespan of Job-Shop production in addition to the optimization scheduling methods,lot splitting may also be utilized opportunely for further optimizing the production plan. A simplified lot splitting Job-Shop scheduling optimization solution is presented and the principle,location,impact on the project,the steps and methods are expounded. According to the restraint of the process route,state variables are used to describe the scheduling process,based on which,a heuristic algorithm is adopted for optimal scheduling. The longest critical path in the optimal scheduling is found out with a kind of algorithm. Three rules should be followed in lot splitting：① After optimizing scheduling first,splitting lot. ② Splitting lot should be chosen at such an equipment that the next equipment on its process route should have free time after finishing the task at the equipment. ③ The equipment -task and at least one of its follow-up processes are on the critical path. Comparing job-process waiting time and track back waiting time,the possible saving makespan between present process and the follow-up processes,the location and size of lot splitting are determined. The lot splitting and optimization reach the goal that the makespan is minimized.

关 键 词：JOB-SHOP 优化算法 调度 批量分解 关键路径 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]