Job shop scheduling techniques in semiconductor manufacturing

This paper presents a brief review on job shop scheduling techniques in semiconductor manufacturing. The manufacturing environment in a semiconductor industry is considered a highly complex job shop, involving multiple types of work centers, large and changing varieties of products, sequence-dependent setup times, reentrant process flow, etc., in a dynamic scheduling environment. Due to the stubborn nature of the deterministic job shop scheduling problem itself, many of the solutions proposed are of hybrid construction cutting across the traditional disciplines. The problem has been investigated from a variety of perspectives resulting in several analytical techniques combining generic as well as problem-specific strategies. In this paper, we seek to provide a brief overview of the problem, the techniques used and the researchers involved in solving this problem.     

考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop 调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop 调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop 调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop 调度问题的优越性能。     

变扰动强度下柔性装配作业车间调度性能分析

柔性装配作业车间是柔性作业车间的一类现实化扩展,其调度问题既要考虑复杂的加工路径柔性,还要考虑零件间的装配关联约束,以及由其带来的关联零件生产进度协同难题。首先给出了柔性装配作业车间调度问题的数学模型;然后考虑现实生产中普遍存在的随机扰动,采用了完全反应式与预测-反应式两类动态调度策略,并提出了相应的优先度规则算法和周期性滚动遗传算法。前者能快速协同各关联任务,但其决策分散,缺乏全局优化力度;后者进行全局周期决策,但扰动将导致性能的下降。最后构建了一般化的仿真模型,并设计了大量的比较实验,分析了不同综合扰动强度对两种调度策略的影响,为实际生产调度策略选择提供了有效的依据。     

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.     

Integrated and events-oriented job shop scheduling

When events such as rush orders or machine breakdown occurs during the production process in a job shop, the delivery date of order may be delayed. To solve this problem, an events-oriented job shop scheduling process is built, and a scheduling model integrated with an enterprise information system (EIS), including Enterprise Resource Planning (ERP), Product Data Management/Computer Aided Process Planning (PDM/CAPP), etc., is proposed and analyzed in detail. A genetic algorithm and a hybrid allocation-based method are used in scheduling. Lastly, an events-oriented job shop scheduling simulation system is presented .     

可变机器约束的模糊作业车间调度问题研究

在车间实际加工中,工件的加工时间和交货期是一个模糊数,而且工件的某道工序有多台机器可供选择。针对这类作业的车间调度,提出了以极大化最小客户满意度为指标的可变机器约束的模糊作业车间调度模型,并给出了算法设计。应用遗传算法在适应度函数处理中引入模糊数处理方法,解决作业车间模糊调度问题,实现调度优化。仿真实验结果表明了该调度方法的有效性,为可变机器约束的模糊作业车间调度提供了一种实现途径。     

Integrated and events-oriented job shop scheduling

When events such as rush orders or machine breakdown occurs during the production process in a job shop, the delivery date of order may be delayed. To solve this problem, an events-oriented job shop scheduling process is built, and a scheduling model integrated with an enterprise information system (EIS), including Enterprise Resource Planning (ERP), Product Data Management/Computer Aided Process Planning (PDM/CAPP), etc., is proposed and analyzed in detail. A genetic algorithm and a hybrid allocation-based method are used in scheduling. Lastly, an events-oriented job shop scheduling simulation system is presented.     

多目标批量生产柔性作业车间优化调度

研究批量生产中以生产周期、最大提前/最大拖后时间、生产成本以及设备利用率指标(机床总负荷和机床最大负荷)为调度目标的柔性作业车间优化调度问题。提出批量生产优化调度策略,建立多目标优化调度模型,结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种群混合算法,以提高搜索效率和搜索质量。仿真结果表明,该模型及算法较目前国内外现有方法更为有效和合理。最后,从现实生产实际出发给出多目标批量生产柔性调度算例,结果可行,可对生产实践起到一定的指导作用。     

Dynamic job-shop scheduling with sequence-dependent setup times: simulation modeling and analysis

This paper presents the salient aspects of a simulation-based experimental study of scheduling rules for scheduling a dynamic job shop in which the setup times are sequence-dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. Simulation experiments were conducted under various experimental conditions characterized by factors such as shop load, setup time ratios, and due date tightness. The results indicate that setup-oriented rules provide better performance than ordinary rules. The difference in performance between these two groups of rules increases with the increase in shop load and setup time ratio. One of the proposed rules performs better for mean flow time and mean tardiness measures.     

分段式车间作业调度算法

车间作业调度问题是制造系统运筹技术、管理技术与优化技术发展的核心。本文对离散作业型 (Job Shop)车间中的作业调度问题做了探讨 ,并根据离散作业调度的阶段性提出了基于作业状态空间的逐段式车间作业调度算法。通过对一个实际车间作业调度仿真比较 ,此算法运算速度比最短加工时间 (SPT)和最少工作量剩余 (L WR)算法快 ,其调度结果具有可执行性     

工艺计划与车间作业计划集成系统的研究

分析了现有工艺计划与车间作业计划的系统集成模型,建立了企业生产工艺计划与作业计划的层次结构,提出了面向车间作业计划的动态、分布式工艺计划与车间作业计划集成模型。将工艺计划与基于周期和事件驱动的动态作业计划相结合,把改进的离散化粒子群算法引入车间优化作业计划运算,使集成模型中生产作业计划与控制功能得以实现。实例证明了集成系统的可行性和有效性。     

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.     

面向IC生产模式的Job Shop调度问题的研究

针对即时定制生产模式的车间调度的特点,提出基于粒子群算法(PSO)的车间调度问题的解决方案.利用粒子群算法本身的优越性解决复杂的车间作业排序问题,克服了传统调度算法存在寻优效率低或全局寻优能力差的弱点.对粒子群的编码及寻优操作进行研究,确定了更适合车间调度问题的编码和操作方式,并将算法进行编程,应用到系统的车间调度部分.仿真结果表明,通过设置适当的参数,可以快速地得到理想的排序结果,能够适用于IC生产模式的车间调度问题.     

Machine Selection Rules in a Dynamic Job Shop

With the increasing use of multipurpose machining centres in job shops, the scheduling problem can no longer neglect multiple job-routes. Existing scheduling approaches seldom address flexibility in job routes and the aim of this paper is to demonstrate that significant improvements to the scheduling performance of dispatching rules can be achieved easily through the use of simple machine selection rules. Three such rules are proposed in this paper and their effectiveness is evaluated through a simulation study of a dynamic job shop. In addition, three dynamic conditions, namely, the tightness of due dates, the flexibility of the job routes and the reliability of the machines, are varied to ensure that the simulation is performed for significantly different job shop conditions. The results of the simulation study indicate that improvements to the performance of simple dispatching rules are significantly enhanced when used with machine selection rules.     

基于遗传-粒子群混合算法的柔性作业车间多资源调度问题

在传统柔性作业车间调度问题(FJSP)中加入运输和装配环节,提出一种柔性作业车间多资源调度问题(MRFJSP),以完工时间最短为目标建立了包含加工、运输和装配的柔性作业车间调度模型。为了提高传统遗传算法(GA)在车间调度问题中的寻优能力,将粒子群算法(PSO)的寻优过程进行改进并与遗传算法进行结合,提出一种带保优策略的遗传-粒子群混合算法,利用单层编码对模型进行求解。通过算例验证了模型的可行性,并将提出的混合算法与遗传算法和粒子群算法进行比较,证明了混合算法的优越性。     

一种解决有AGV小车约束的车间智能调度问题的算法

考虑AGV小车在车间调度中只参与运输工件的特点和小车的运输路线对工件工艺路线选择的影响，分析了在机床／AGV小车双资源约束下的车间调度问题，讨论了AGV小车在车间调度中的调度机制。在分析问题的基础上建立了有AGV小车参与调度的车间调度问题的数学模型，并提出了基于遗传算法的机床／AGV小车的调度算法，论述了编码、选择和变异操作的规则，提出了工序特征的交叉算子。仿真结果表明，该算法是可行的，可以获得比较好的效果，为在AGV小车约束下的车间调度提供了一种有效的实践途径。     

Group shop scheduling with uncertain data and a general cost objective

In this paper, a stochastic group shop scheduling problem with a due date-related objective is studied. The group shop scheduling problem provides a general formulation including two other shop scheduling problems, the job shop and the open shop. Both job release dates and processing times are assumed to be random variables with known distributions. Moreover, earliness and tardiness of jobs are penalized at different rates. The objective is to minimize the expected maximum completion cost among all jobs. A lower bound on the objective function is proposed, and then, a hybrid approach following a simulation optimization procedure is developed to deal with the problem. An ant colony optimization algorithm is employed to construct good feasible solutions, while a discrete-event simulation model is used to estimate the performance of each constructed solution that, taking into account its lower bound, may improve the best solution found so far. The proposed approach is then evaluated through computational experiments.     

基于效率函数的双资源约束作业车间调度算法

目前对制造业领域作业车间调度问题研究中,仅考虑单一设备资源的传统作业车间调度问题已不能反应出实际作业车间的作业环境。根据实际作业车间多资源环境,建立了分别最小化生产完工期和超期时数为目标函数的设备和模具双资源约束作业车间调度模型,并采用基于效率函数的逆序调度算法对问题进行求解。最后,通过实例对算法进行验证并给出对比结果。     

基于遗传算法的作业车间调度研究与应用

提高大功率船舶柴油机的生产能力和水平,对提高我国造船行业的国际竞争力有着重要的意义。介绍作业车间调度问题,提出一种改进的遗传算法,同时将此算法应用于船舶柴油机的作业车间调度,该算法采用基于工序的编码方式,考虑了机床与工艺路线的约束,求解以关键设备的利用率最高和产品的加工周期最短为目标的静态调度问题,并通过具体的实例仿真分析其有效性。     

求解作业车间调度问题的快速启发式算法

首先将作业车间调度问题转换为一个搭积木模型,受这个直观模型的启发,提出了一个启发式的搭积木规则,该规则综合考虑了已经搭好的积木的顶高和将要搭积木的剩余高度。基于这个规则,提出了一个求解作业车间调度问题的快速启发式算法,对国际上通用的benchmark例的模拟实验结果表明,提出的算法优于经典的优先分配启发式算法。