多目标柔性作业车间稳健性动态调度研究

研究了以调度稳定性和鲁棒性为优化目标的柔性作业车间动态调度问题。建立了多目标柔性作业车间动态调度问题模型;针对动态事件特点,采用工件到达发生器和机器故障预维护发生器模拟动态事件,提出了基于周期与事件驱动的混合重调度策略,该策略在每个重调度点对工件进行完全重调度或右移重调度;为克服传统差分算法早熟的缺点,设计了一种改进的多目标差分进化算法求解该调度问题;实例验证了提出策略和算法的有效性。     

DYNAMIC ADVANCED PLANNING AND SCHEDULING WITH FROZEN INTERVAL FOR NEW ORDERS

A dynamic advanced planning and scheduling(DAPS)problem is addressed where new orders arrive on a continuous basis.A periodic policy with frozen interval is adopted to increase stability on the shop floor.A genetic algorithm is developed to find a schedule at each rescheduling point for both original orders and new orders that both production idle time and penalties on tardiness and earliness of orders are minimized.The proposed methodology is tested on a small example to illustrate the effect of the frozen interval.The results indicate that the suggested approach can improve the schedule stability while retaining efficiency.     

A rolling horizon job shop rescheduling strategy in the dynamic environment

In this paper, the job shop scheduling problem in a dynamic environment is studied. Jobs arrive continuously, machines breakdown, machines are repaired and due dates of jobs may change during processing. Inspired by the rolling horizon optimisation method from predictive control technology, a periodic and event-driven rolling horizon scheduling strategy is presented and adapted to continuous processing in a changing environment. The scheduling algorithm is a hybrid of genetic algorithms and dispatching rules for solving the job shop scheduling problem with sequence-dependent set-up time and due date constraints. Simulation results show that the proposed strategy is more suitable for a dynamic job shop environment than the static scheduling strategy.     

基于Agent的生产调度混合协商策略研究

当前大多协商策略无法兼顾规划和反应能力,为此,本文提出一种短期规划与动态响应能力相结合的混合协商策略。该策略针对柔性车间生产调度问题和面对扰动的再调度问题,将组合拍卖与改进合同网相结合,通过规定相关智能体的动作和交互顺序,实现系统在平稳或扰动状态下的生产调度。基于上述协商策略,开发了一个基于智能体的生产调度原型系统,并通过仿真实验验证协商策略的可行性和有效性。     

Sensitivity search for the rescheduling of semiconductor photolithography operations

This study deals with the rescheduling problem of the photolithography area in semiconductor wafer fabrications. The objective is to find a schedule that minimizes the weighted sum of makespan, maximum tardiness, and total setup time. Practical issues such as machine breakdowns, limited number of available masks, restrictions on photoresist, production notice, and machine setup are considered. Three popular search algorithms—simulated annealing (SA), genetic algorithm (GA), and tabu search (TS) — are tested to solve the scheduling problem. We also propose a new sensitivity search approach. A new event changes the scheduling problem. Thus, the problem needs to be re-solved to reflect such changes. In an actual production environment, we propose that, instead of searching for a solution from scratch, the search process can be restarted from the best solution of an original problem that is very similar to the new problem. Using an industrial data set, this study tests the proposed approach. The results show that TS performs the best among the algorithms tested, and the performance of the sensitivity TS significantly surpasses that of the traditional approach.     

前移存在调整时间综合调度工序的算法

针对目前存在调整时间的综合调度算法只考虑快速插入调整时间实现调度方案,没有考虑调整时间会随工序次序改变影响调度结果的问题,提出通过改变工序调度次序前移存在调整时间综合调度工序的算法。该算法在保证相关工序不后移的条件下,通过改变相同加工设备上具有相同工艺紧后工序的工序调度次序,从而改变工序之间的调整时间,使调整工序最晚结束时间提前,使其工艺紧后工序开始时间有可能提前,从而实现提高设备利用率,提前产品最终完工时间。实例表明该算法可获得存在调整时间的综合调度问题的更优解。     

基于模糊神经网络的半导体生产线重调度策略优化

针对缺乏半导体生产线重调度策略优化方法的研究现状,提出了基于模糊神经网络的半导体生产线重调度策略优化技术。将重调度策略划分为半导体生产线、设备组和设备重调度层次,利用仿真评价确定优化的重调度策略,并获得样本数据。通过对模糊神经网络训练,建立干扰和半导体生产线状态等输入参数与优化的重调度策略输出之间的映射关系。以上海某125mm晶圆生产线为例,结果表明了该重调度策略优化方法的有效性。     

基于遗传算法和分枝定界的多车间空闲产能调度方法

个性化产品具有多变的产品结构和复杂的加工特征,使得单一车间难以满足如此广泛的加工参数,需要借助外协车间才能完成生产任务。每个外协车间负载不同,空闲时段也不同,为了提升这些时间的利用率,提出基于遗传算法和分枝定界的混合调度方法。设计基于混合优化策略的动态重调度机制,将动态的生产过程转化为一系列在时间上连续的静态调度问题;建立以最小化总拖期为目标的数学模型;采用遗传算法和分枝定界方法对调度过程中的两个阶段分别进行优化,即在每个事件时刻采用遗传算法生成预调度方案并划分为已派工部分、待派工部分和可调整部分,在已派工部分正在执行的时间段采用分枝定界方法对可调整部分进行改进优化。采用运筹学优化器OR-Tools验证所提模型的正确性。试验数据表明,与单一方法相比,混合方法在所有实例上获得改进,验证了所提方法是有效可行的。     

Greedy randomised dispatching heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we present greedy randomised dispatching heuristics for the single-machine scheduling problem with quadratic earliness and tardiness costs and no machine idle time. The several heuristic versions differ, on the one hand, on the strategies involved in the construction of the greedy randomised schedules. On the other hand, these versions also differ on whether they employ only a final improvement step or perform a local search after each greedy randomised construction. The proposed heuristics were compared with existing procedures as well as with optimum solutions for some instance sizes. The computational results show that the proposed procedures clearly outperform their underlying dispatching heuristic, and the best of these procedures provide results that are quite close to the optimum. The best of the proposed algorithms is the new recommended heuristic for large instances as well as a suitable alternative to the best existing procedure for the larger of the middle-sized instances.     

NEW NONSTANDARD JOB SHOP SCHEDULING ALGORITHM

Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.     

带多处理器任务的动态混合流水车间调度问题

研究了具有多处理器任务的混合流水车间调度问题,且考虑相邻两阶段之间的运输时间、机器故障和工件动态到达的实际生产特征。由于该问题不但求解非常复杂,对它的不同部分的简化还会使其变成其他不同的典型调度问题,探讨该类问题的近似解法具有挑战性和广义性。据此分别采用结合次梯度算法的拉格朗日松弛算法、结合次梯度和bundle算法的交替算法（交替S＆B算法）的拉格朗日松驰算法进行求解。对多达100个工件的问题进行测试,结果表明,所设计的算法能够在合理的CPU时间内产生较好的时间表。     

基于Memetic算法的车间动态调度策略研究

针对车间动态调度问题的求解,提出了一种基于Memetic算法的车间动态调度策略。该策略结合滚动窗口机制,并采用基于周期和事件的混合驱动策略,运用Memetic算法对每个滚动窗口工件集进行重调度。该算法采用顺序交叉算子和基于邻域搜索的新型变异算子,在交叉和变异后均采用改进的模拟退火策略进行局部搜索。通过对改进后的基准实例进行实验,验证了该策略的有效性。
     

A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions

In most real manufacturing environment, schedules are usually inevitable with the presence of various unexpected disruptions. In this study, a new rescheduling technique based on a hybrid intelligent algorithm is developed for solving job shop scheduling problems with random job arrivals and machine breakdowns. According to the dynamic feature of this problem, a new initialization method is proposed to improve the performance of the hybrid intelligent algorithm, which combines the advantage of genetic algorithm and tabu search. In order to solve the difficulty of using the mathematical model to express the unexpected disruptions, a simulator is designed to generate the disruptions. The performance measures investigated respectively are: mean flow time, maximum flow time, mean tardiness, maximum tardiness, and the number of tardy jobs. Moreover, many experiments have been designed to test and evaluate the effect of different initializations in several disruption scenarios. Finally, the performance of the new rescheduling technique is compared with other rescheduling technologies in various shop floor conditions. The experimental results show that the proposed rescheduling technique is superior to other rescheduling techniques with respect to five objectives, different shop load level, and different due date tightness. The results also illustrate that the proposed rescheduling technique has a good robustness in the dynamic manufacturing environment.     

[智能设计与计划调度]机器故障下加工车间优化重调度方式预测

为预知不同故障情形下的优化重调度方式,实现快速、有效的重调度决策,提出融合调度仿真与改进概率神经网络的重调度方式预测方法。考虑到现场故障样本难获得且无法涵盖全部故障情形,利用仿真实现随机故障下优化重调度样本的生成;以工序加工时间的累计变动、变动任务数、makespan改变量为决策依据,生成各样本的标签;将带标签数据样本输入到概率神经网络模型,实现优化重调度方式预测。实验结果表明：所提出的方法准确率达99.54%;在指定加工车间和生产任务的前提下,故障机序号和故障修复时间对优化重调度方式起决定性作用。     

流水车间作业提前/拖期调度问题研究

在非正规性能指标提前／拖期调度问题中,工件的加工顺序和每个加工活动的开始时刻都属于需要优化的变量,增加了求解的难度。针对这一问题,提出了采用分层调度模式求解流水车间提前／拖期调度问题的联合算法。首先,采用遗传算法对加工顺序进行寻优;其次,在给定调度序列的情况下采用启发式算法对加工开始时刻进行优化,制定插入机器空闲时段的策略,确定何时插入空闲时段和空闲时段的大小,即在给定顺序下确定工件加工活动的开始时刻,以满足在加工完所有工件后,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该联合算法的有效性。     

多工艺路线的批量生产调度优化

以优化生产周期为目标,研究了多工艺路线的批量调度问题,提出了一种基于工序优先级的调度算法,并将该算法嵌入到遗传算法中,得到了全局优化的批量调度算法。遗传算法搜索最佳染色体,调度算法把染色体解码为调度。在调度算法中,采用了3种提高生产率的策略,即区分批量启动时间与工序加工时间,在工件到达机床之前做好准备工作;把一批工件分成多个小生产批次,每批次独立加工:一批工件加工部分后就运向后续加工机床,缩小后续机床的等待时间。仿真表明,该调度方法能取得较好结果。     

A particle swarm optimization for multi-objective flowshop scheduling

The academic approach of single-objective flowshop scheduling has been extended to multiple objectives to meet the requirements of realistic manufacturing systems. Many algorithms have been developed to search for optimal or near-optimal solutions due to the computational cost of determining exact solutions. This paper provides a particle swarm optimization-based multi-objective algorithm for flowshop scheduling. The proposed evolutionary algorithm searches the Pareto optimal solution for objectives by considering the makespan, mean flow time, and machine idle time. The algorithm was tested on benchmark problems to evaluate its performance. The results show that the modified particle swarm optimization algorithm performed better in terms of searching quality and efficiency than other traditional heuristics.     

安全和容错的网格任务调度

为解决跨自治域的网络任务调度中的安全性和容错问题,提出了基于网格安全和容错的网格任务调度算法,并对用户任务的安全需求和资源的信任等级进行匹配,在系统安全等级较低且网络和主机可能失效的网格环境中进行容错任务调度。该算法根据网格系统的安全等级,自适应调整任务备份数,并对失败的任务重新调度。仿真结果表明,该算法可以有效提高不安全网格环境下的任务调度成功率,具有很好的容错性和可扩展性。     

Advanced planning and scheduling for TFT-LCD color filter fab with multiple lines

Intense global competition and declining profit have caused most thin film transistor liquid crystal display manufacturers to increase their competitiveness by improving productivity and reducing cycle times. An advanced planning and scheduling (APS) system was developed with Microsoft Visual Basic for Application to automatically generate production schedules for a color filter fab with multiple lines. This system can assign orders to production lines, plan order release time, and balance the equipment loading. Both forward scheduling and backward scheduling were used in APS. Experimental results indicated that APS can significantly reduce manual scheduling time while maintaining the quality of scheduling results. Compared to manual operations, it can save more than 87 % of scheduling time and the quickness is especially important when rescheduling is needed due to production uncertainties such as equipment breakdown or material shortage. Production controllers can use this APS to generate initial schedule and make adjustment based on experience.     

基于新型邻域结构的混合算法求解作业车间调度

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况:直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。