基于交货期紧迫度的综合调度算法

为解决开始时间与交货期都不相同的多品种小批量复杂产品综合调度问题,提出基于交货期紧迫度的综合调度算法。该算法根据产品加工的开始时间由前到后排序调度;当存在多产品开始时间相同时,根据产品优先加工的紧迫度,确定它们的调度次序;如果存在紧迫度相同的产品,将按交货期由早到晚排序调度;若交货期也相同,则将它们虚拟成一个产品统一调度;对被调度产品采用长路径策略和短用时策略确定其各工序的调度次序,并结合设备工序紧凑法确定工序的开始时间。该算法结合产品紧迫度和设备工序紧凑法的优点,使开始时间不同的多产品在尽量减少设备空闲时间的情况下,按交货期完工。理论分析和实例表明,该算法可在二次复杂度内给出较合理的综合调度方案。

蚁群算法及其在有硬时间窗的车辆路径问题中的应用

为求解有硬时间窗的车辆路径问题,提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法。在第一阶段,用蚂蚁的局部遍历代替传统的全局遍历,每个蚂蚁采用蚁群算法进行局部遍历,构造一个回路,蚂蚁转移采用回路两阶段构路策略;在第二阶段,由前一阶段所构造的回路通过采用近似解可行化策略来组合形成可行解。此外,为提高算法的寻优能力,在转移规则中引入了基于时间窗的紧迫性因子和匹配度因子,并与节约算法和爬山法有机结合。实验结果表明,自适应混和蚁群算法性能优良,能够有效地求解有硬时间窗的车辆路径问题。

基于Petri网的改进检验过程调度算法

原材料的检验方法在生产计划中起着关键的作用。根据检验过程的特点,提出一种改进的检验过程调度算法。该算法解决了此前多处理器调度算法用于分支检验时仅根据原材料投产时间对材料进行调度所产生的问题。改进的算法增加了原材料检验任务的紧迫度的概念,针对检验时间较长的材料,投产时间紧迫的任务实现了有效调度,进而提高生产效率。同时算法结合高级颜色时间Petri网,模拟一个实际企业管理系统,对改进的检验任务调度算法建模并进行仿真测试。测试结果表明,改进的算法在生产计划的检验过程中,检验成功率和检验员的工作效率较先前算法都有较大提高。

一种基于紧急程度的自时钟开始时间公平排队分组调度算法

为了克服目前GPS(Generalized Processor Sharing)类调度算法中实时应用分组的排队时延较大且不稳定的局限性,该文提出一种新的分组排队调度算法,该调度算法在计算分组服务标签时添加了一个紧急程度函数,调整了到达分组间的竞争关系,从而可以按照实时性应用的要求来调整到达分组的转发先优级,由此显著降低了实时性应用分组的排队时延和抖动幅度。分析和仿真实验表明,与GPS类其它调度算法相比,该调度算法对于实时应用的分组能提供较低的、更稳定的排队时延保证,同时还继承了GPS类算法的公平性和排队时延有界等特性,而且对系统虚拟时间的跟踪计算更为简捷高效。

考虑工序序列动态时间紧迫度的逆序贪婪综合调度算法

针对树状结构复杂单产品加工和装配的一般综合调度问题,该文提出考虑工序序列动态时间紧迫度(TUD)的逆序贪婪综合调度算法。提出工序排序策略,定义工序序列的时间紧迫度,将工序树逆置,采用叶对齐的方式,按照由叶到根的顺序,逐层根据叶结点所属工序序列动态时间紧迫度值由大到小的顺序确定其调度顺序,将各层排序后的叶结点依次入队列保存,最后将队列中元素逆置。提出逆序贪婪调度策略,每次以一道工序为单位,安排它在所需设备上的准调度时间点进行试调度,得到该工序的准调度方案集,选择准调度方案结束时间最小的方案,若不唯一,选择使该工序尽早加工的方案。实例表明所提算法优化了一般综合调度的结果且效率较高。