资源约束的高层次数据流调度方法

提出遗传算法和蚂蚁算法动态融合解决资源约束调度问题的方法.讨论资源约束调度过程中遗传算法的编码规则,蚂蚁算法中蚂蚁的概率选择方法和信息素更新规则,给出两种算法的动态切换条件及如何由遗传算法的调度结果产生蚂蚁算法的初始信息素分布等,实验数据表明本文方法的稳定性、平均运行时间和平均调度结果均优于单独的遗传算法和蚂蚁算法.     

基于两阶段求解算法的动态车辆调度问题研究

在分析需求动态变化的基础上,根据需求信息的提出顺序,将动态配送问题转换成不同时刻的静态车辆调度问题,建立基于时间轴的动态车辆调度模型;利用量子理论改进遗传算法,设计量子遗传算法;针对动态车辆调度问题实时性强的特点,设计＂初始优化阶段＋实时优化阶段＂的两阶段求解策略,通过信息更新插入动态需求客户,并对已产生的计划路径进行局部优化调整.通过仿真计算,验证了模型和算法的有效性.     

基于人机交互的炼钢连铸动态调度*

针对炼钢连铸动态调度问题,建立了问题的优化模型、设计了约束满足求解算法并分析了算法复杂度、开发了炼钢连铸动态调度的人机交互系统。当生产过程中的扰动事件发生时,系统能够通过人机交互并结合优化模型和多项式时间复杂度的算法获得可行且与原调度尽量一致的新调度方案,以确保动态调度前后整个生产过程的连续性和稳定性。     

混合粒子群算法在job-shop动态调度中的应用

提出了基于事件驱动的动态调度策略,以融合遗传算法的粒子群算法来实现作业车间生产调度,有很好的收敛精度;在此基础上,对作业车间生产调度中的工件增加及取消、机器故障等各种动态事件进行了研究,能在扰动后提供新的调度计划,有效地解决了车间动态调度的一致性和连续性的问题。     

多目标环境下的生产资源平衡和优化调度研究

基于调度周期订单所映射的工件集合,讨论了以生产资源和工艺方案为约束的多工艺方案推荐方法,有目的地为生产调度进行工艺选择,提高生产调度的运行效率.基于遗传算法,考虑设备负荷均衡、关键设备利用率、所有设备利用率等多目标,进行了基于可用资源的生产调度基础数据优化处理.结合实例,根据不同的目标得到了有效的可选工艺方案,仿真结果表明,经过生产资源平衡后,较易得到满意的调度方案.     

Tabu搜索算法在电话网智能管理中的应用

针对电话网智能管理系统中动态路由方案的实现,研究了采用Tabu搜索算法解决路由方案的问题.对Tabu搜索算法作了改进,使得它可以用来解决电话网的电路自动调度问题,并且得到了较好的结果.改进后的Tabu算法与遗传算法相比,能够在较短的时间内计算得到全局优化的路由方案.该算法正在广东省电话网智能管理系统中所使用.     

基于FJ的多版本类动态更新演算

针对面向对象软件在动态更新中遇到类型安全问题,定义了一个多版本类的动态更新演算(MCUFJ演算(multi-version class dynamic updamble calculus based on FJ calculus))来描述类动态更新.MCUFJ演算以FJ(featherweight Java)演算为核心,通过增加update操作表示类的动态更新,运用多版本技术使动态更新可以在保持新旧对象共存的情况下完成,讨论了类的数据域和方法进行增加、删除、修改以及类型变化对程序类型安全性的影响,并且指出MCUFJ上类型安全的动态更新需要满足的约束.定义了类的可动态更新限制,并且证明了在该条件下多版本类的动态更新在类型上的安全性.该演算可以用于指导Java语言和面向对象程序语言的类动态更新.     

一类新的动态车辆调度问题的建模与算法

针对目前对于动态车辆调度问题的研究仅集中于考虑时间依赖或依概率变化的情形,在对原有动态车辆调度问题模型进行总结的基础上,综合考虑了时间依赖且网络依概率变化,以及结合带有时间窗和随机需求的情况,提出了新的问题模型,并提出求解该问题模型的多目标随机机会约束规划模型,设计了用遗传算法解决该模型的方案与步骤。实验结果表明,所提出的模型可有效地拟合交通状况,设计的算法可以有效地求解该模型。     

基于窗口的印刷车间作业动态调度研究

为了解决实际印刷车间突发设备故障和紧急插单问题,采用滚动窗口技术结合遗传算法的方法,建立适合实际印刷车间生产的动态再调度模型;设定若干印品订单、机器设备的加工工序以及各工序加工时间、工序约束条件等,以订单的最大最小加工时间和再调度的偏离度为多目标优化,采用周期与事件混合驱动策略,将滚动窗口再调度机制和遗传算法相结合进行流程设计和编码,构建印刷车间再调度模型;采用标准问题FT06和FT01验证了文章设计的模型算法的有效性和可行性;运行程序,模拟正常加工时紧急插单和机器故障突发时,系统生产新的调度计划即调度甘特图,仿真结果表明该动态调度模型可以用于印刷作业的正常排产调度,在遇突发状况时可生成稳定、符合交货日期的再调度方案。     

炼钢机器故障下炼钢-连铸调度DCSP建模与算法

针对机器故障下的炼钢-连铸动态调度问题,基于动态约束满足技术开发了能够灵活反映各种动态因素的建模机制。从变量、值域和约束三个角度将生产过程中的机器故障的影响映射为约束满足模型的动态变化;提出了重调度前后调度方案在时间安排和机器指派上的一致性度量方法,以满足不同炉次对时间和机器一致性的不同要求;将机器故障扰动按影响程度分为3个层级,建立了故障扰动与约束满足调度模型间的映射关系。根据炼钢、精炼阶段的机器故障扰动程度,制定不同的求解策略,并为机器指派变量赋值;基于约束传播技术,通过调整开工时间和柔性加工时间分步消解时间约束冲突。仿真实验表明,提出的模型和算法是可行和有效的。     

GA-based discrete dynamic programming approach for scheduling inFMS environments

The paper presents a new genetic algorithm (GA)-based discrete dynamic programming (DDP) approach for generating static schedules in a flexible manufacturing system (FMS) environment. This GA-DDP approach adopts a sequence-dependent schedule generation strategy, where a GA is employed to generate feasible job sequences and a series of discrete dynamic programs are constructed to generate legal schedules for a given sequence of jobs. In formulating the GA, different performance criteria could be easily included. The developed DDF algorithm is capable of identifying locally optimized partial schedules and shares the computation efficiency of dynamic programming. The algorithm is designed In such a way that it does not suffer from the state explosion problem inherent in pure dynamic programming approaches in FMS scheduling. Numerical examples are reported to illustrate the approach.     

Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine.     

Fuzzy rule generation for adaptive scheduling in a dynamic manufacturing environment

This paper proposes a fuzzy rule-based system for an adaptive scheduling, which dynamically selects and applies the most suitable strategy according to the current state of the scheduling environment. The adaptive scheduling problem is generally considered as a classification task since the performance of the adaptive scheduling system depends on the effectiveness of the mapping knowledge between system states and the best rules for the states. A rule base for this mapping is built and evolved by the proposed fuzzy dynamic learning classifier based on the training data cumulated by a simulation method. Distributed fuzzy sets approach, which uses multiple fuzzy numbers simultaneously, is adopted to recognize the system states. The developed fuzzy rules may readily be interpreted, adopted and, when necessary, modified by human experts. An application of the proposed method to a job-dispatching problem in a hypothetical flexible manufacturing system (FMS) shows that the method can develop more effective and robust rules than the traditional job-dispatching rules and a neural network approach.     

Scheduling of Virtual Cellular Manufacturing Systems: A Biogeography-Based Optimization Algorithm

Virtual cellular manufacturing system (VCMS) is one of the modern strategies in the production facilities layout, which has attracted considerable attention in recent years. In this system, machines are located in different positions on the shop floor and virtual cells are a logical grouping of machines, jobs, and workers from the viewpoint of the production control system. These features not only enhance the system’s agility but also allow a dynamic reassignment of cells as demand changes. This paper addresses the VCMS scheduling problems where the jobs have different orders on machines and the objective is to simultaneously minimize the weighted sum of the makespan and total traveling distance in order to create a balance between criteria. The research methodology firstly consists of a mathematical programming model with regard to the production constraints in order to describe the characteristics of the VCMS. Secondly, a basic genetic algorithm (GA), a biogeography-based optimization (BBO) algorithm, an algorithm based on hybridization of BBO and GA, and the BBO algorithm accompanied by restart phase are developed to solve the VCMS scheduling problems. The developed algorithms have been compared to each other and their performance are evaluated in terms of their best solution and computational time as effectiveness and efficiency criteria, respectively. Consequently, the performance of the best algorithm has been evaluated by the state-of-the-art algorithm, GA, in the literature. The results show that the best algorithm based on BBO could find solutions at least as good as the last famous algorithm, GA, in the literature.     

双资源生产车间调度问题的研究

将遗传算法(GA)和模拟退火算法(SA)相结合研究了双资源生产车间的调度优化问题,该混合算法将机床设备和工人合理地分配给加工任务,使评价性能指标获得最优。通过与国内外学者的算法进行比较,本算法获得的生产周期最短,机床利用率和工人利用率都较高,并且在某些情况下,平均流动时间也较短。因此可以证明本算法具有一定的优越性。     

LEARNING-BASED SCHEDULING OF FLEXIBLE MANUFACTURING SYSTEMS USING SUPPORT VECTOR MACHINES

Dispatching rules are usually applied to dynamically schedule jobs in flexible manufacturing systems (FMSs). Despite their frequent use a significant drawback is that the performance level of the rule is dictated by the current state of the manufacturing system. Because no rule is better than any other for every system state, it would be highly desirable to know which rule is the most appropriate for each given condition. To achieve this goal we propose a scheduling approach using support vector machines (SVMs). By using this technique and by analyzing the earlier performance of the system, “scheduling knowledge” is obtained whereby the right dispatching rule at each particular moment can be determined. Simulation results show that the proposed approach leads to significant performance improvements over existing dispatching rules. In the same way it is also confirmed that SVMs perform better than other traditional machine learning algorithms as the inductive learning when applied to FMS scheduling problem, due to their better generalization capability.     

一种基于预测的资源匹配算法

网格任务调度过程中的资源匹配是根据任务要求从网格资源信息服务（GRIS）中查找出合适资源的过程。GRIS中记录的往往是资源的静态信息，由于本地负载的动态变化使得基于资源静态信息来确定的候选资源集中一些资源并不能满足任务的QoS需求。基于相关资源动态信息预测资源未来状态，给出了网格任务平均完成时间及完成时间的分布函数，并根据任务QoS需求，兼顾考虑资源当前及未来状态，提出了一种资源匹配模型与匹配算法。通过实验表明，该算法能有效减少候选资源数目，从而降低调度时间复杂度。     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

基于Hadoop的三队列作业调度算法

Hadoop集群单队列作业调度会产生短作业等待、资源利用率低的问题;采用多队列调度可兼顾公平、提高执行效率,但会带来手工配置参数、资源互占、算法复杂等问题。针对上述问题,提出三队列作业调度算法,利用区分作业类型、动态调整作业优先级、配置共享资源池、作业抢占等设计,达到平衡作业需求、简化一般作业调度流程、提升并行执行能力的目的。对短作业占比高,各作业占比均衡以及一般作业为主,偶尔出现长、短作业三种情况与先进先出(FIFO)算法进行了对比实验,结果三队列算法的运行时间均比FIFO算法要少。实验结果表明,在短作业聚集时,三队列算法的执行效率提升并不显著;但当各种作业并存且分布均衡时,效果很明显,这符合了算法设计时短作业优先、一般作业简化流程、兼顾长作业的初衷,提高了作业整体执行效率。     

基于双层规划的容器云资源动态配置算法

本文分析容器云资源动态配置决策问题,通过定义容器云资源的调度任务,求解得到容器云资源调度时间;利用容器云资源调度任务的最短时间矩阵,获取容器云资源调度所需的条件。在双层规划条件下,求解容器云资源调度的目标函数和约束函数;考虑到用户的任务情况和云数据中心的云资源状况,在虚拟机上构建一个到物理主机的矩阵,通过构建容器云资源动态配置结果在优化时的目标函数,结合约束条件,实现容器云资源的动态配置。实验结果表明,资源动态配置算法不仅可以提高容器云资源的利用率,还可以减少配置完成时间,具有更好的动态配置性能。