参考资料--车间作业调度算法初步研究.docxVIP

一种车间作业调度算法的初步研究摘 要：车间作业调度是MES的核心模块,直接关系着企业的经营、生产和管理效率,有效的调度方案能最大限度地降低生产成本,提高企业竞争力。车间作业调度问题也是一种典型的组合优化问题,关于它的研究具有很大的现实意义,也有一定的理论意义。论文介绍一种基于规则的优化调度算法,以相对剩余工时最长为条件或调度规则,进行优化调度操作。关键词：MES，车间作业调度，调度规则，相对剩余工时Abstract: The workshop scheduling management is the core module of MES, which greatly affects the efficiency, operation and management of workshop. Effective scheduling can reduce production cost and enhance enterprise competitiveness. The workshop scheduling is a typical combinatorial optimization problem. It has both practical significance and theoretical value for studying it. The paper introduces a rule-based optimization algorithm, with the longest duration as a condition of relative rest or scheduling rules to optimize the scheduling operations.Key words: MES, Job-shop scheduling, Scheduling rules, Remaining duration1 引言 目前，在离散型制造企业中，多采用小批量、单件、多品种为生产方式，而单件车间调度问题是一个代表性的作业调度问题。关于单件车间的调度问题，目前的研究的成果也较多，比如遗传算法、神经网络方法和分支定界法等。在理论上这些方法的探索较多，并且对小规模的调度与应用效果较好。但是，由于车间调度问题的复杂性，当工件数量与机器数量都比较多的情况下，上述算法在PC上运行的时间比较长，工程实际中的应用也不太理想。 在业界基于启发式规则的调度算法被公认为最具有工程实用价值，所谓规则调度是安装一定的准则对加工的设备和加工的任务进行优先级的排序。目前，投入使用的调度系统大多采用规则调度算法。启发式优先分配的方法有较小的时间复杂性和容易实现的特点，因而在实际求解调度问题中经常使用这个方法。而规则调度算法的关键问题是要选择好优先分配的规则，本文将剩余工期最大且工期较短作为分配的规则。2 调度规则 车间作业调度问题(Job-Shop Scheduling Problem，JSSP)是一个典型组合优化的问题。所谓组合优化问题，就是指从组合问题的可行解集合中寻找最优解。此问题有三个基本的要素，即变量、约束和目标函数。例如在实际调度过程中，对工序的加工排序以及对相应设备的选择都是调度过程中的变量，工序的工艺路线以及其相互间的关系都是对变量的约束，作业调度的目标有加工总时间最短、设备利用率最高、工件按期交货等。关于在m台设备上加工n个工件的调度问题，最有效的方法之一是按优先规则进行排序。以某些方式评价各竞争工序是优先规则的目的，从而方便在加工设备空闲的情况下，可以确定下一个需要调度执行的工序。此方法不仅可以简化排序的过程、减少工作量和提高排序的速度，而且能够给出比较优的方案。2.1 描述问题的变量 关于车间作业调度问题可以描述为，n个不同的工件和m台不同的机器，每一个工件都是由一个或多道工序组成的工序集合，并且同一工件工序的顺序是给定的，在工件所要求的机器和固定的工期下，完成每一个工序。机器与工件间的约束有，某一个工序开始之后不能被中断、属于不同工件的工序没有先后开工的约束，某个机器最早开工时间及实际已经下达的加工工序的结束时间会影响工序的最早开工时间、每一台机器同时只能加工一个工件或被一个工件使用。在描述问题的时候，用到的变量有，m－机器的数量、n－任务的数量、Ai－任务所包含的工序的数目、－表示任务的第 j 道工序、－在调度阶段t,工序的完工日期、－在调度阶段t,工序的开工日期、T－调度的总阶段数,其等于工序的总数量 n×m、－工序 的工期， = - 、－工序对应的任务i在调度阶段t 的完工时间、－机器 i 需要加工的任务集合，i=1,2,…,m、－任务i 最早的可能开工日期、－在阶段t, 对机器K形成竞争的可以调度的工序集