A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem

Job shop scheduling is an important decision process in contemporary manufacturing systems. In this paper, we aim at the job shop scheduling problem in which the total weighted tardiness must be minimized. This objective function is relevant for the make-to-order production mode with an emphasis on customer satisfaction. In order to save the computational time, we focus on the set of non-delay schedules and use a genetic algorithm to optimize the set of dispatching rules used for schedule construction. Another advantage of this strategy is that it can be readily applied in a dynamic scheduling environment which must be investigated with simulation. Considering that the rules selected for scheduling previous operations have a direct impact on the optimal rules for scheduling subsequent operations, Bayesian networks are utilized to model the distribution of high-quality solutions in the population and to produce the new generation of individuals. In addition, some selected individuals are further improved by a special local search module based on systematic perturbations to the operation processing times. The superiority of the proposed approach is especially remarkable when the size of the scheduling problem is large.     

Performance Modelling and Evaluation of Dynamic Tool Allocation in Flexible Manufacturing Systems using Coloured Petri Nets: An Object-Oriented Approach

Manufacturing systems are faced with ever-increasing customisation and unstable demand. The traditional hierarchical control structures for shop floor (pre-release planning, scheduling, dispatching and activity control) are often inflexible in responding to unexpected scenario changes and are thus not robust to system disturbances. In this paper, an object-oriented approach to modelling of FMS dynamic tool allocation and control under a non-hierarchical shop floor control scheme using coloured Petri nets is presented. A client–server paradigm is used in the proposed modelling method. The complete FMS model is partitioned into individual classes (machines, magazines, tool transport system, SGVs, tool storage, etc.) thereby significantly reducing the complexity of the model to a tractable size. The system performance under different tool request selection rules is also evaluated using coloured Petri net simulation. The proposed method can provide the designer of a tool management system with a high-level and structured representation of the tool-sharing control. It also provides an effective method for prototyping and evaluating performance of object-oriented shop floor control software.     

基于数字孪生的复杂产品离散装配车间动态调度

面向多品种变批量生产的复杂产品离散装配车间是典型的复杂制造系统,其运行过程呈现高复杂性、强动态性和不确定性因素多等特征,为实现复杂产品离散装配车间的动态调度,提出一种基于数字孪生的复杂产品离散装配车间动态调度方法,通过物理空间和虚拟空间之间的数据交互进行更精确的动态调度。构建了基于数字孪生的复杂产品离散装配车间调度框架和调度问题模型,详细阐述了基于实时数据和神经网络的工时在线预测、面向复杂产品离散装配的数字孪生车间动态调度等关键实现技术;构建了复杂产品离散装配车间调度系统,并以某航天产品装配车间的调度过程为例,验证了该方法的有效性和可行性。     

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

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

Learning iterative dispatching rules for job shop scheduling with genetic programming

This study proposes a new type of dispatching rule for job shop scheduling problems. The novelty of these dispatching rules is that they can iteratively improve the schedules by utilising the information from completed schedules. While the quality of the schedule can be improved, the proposed iterative dispatching rules (IDRs) still maintain the easiness of implementation and low computational effort of the traditional dispatching rules. This feature makes them more attractive for large-scale manufacturing systems. A genetic programming (GP) method is developed in this paper to evolve IDRs for job shop scheduling problems. The results show that the proposed GP method is significantly better than the simple GP method for evolving composite dispatching rules. The evolved IDRs also show their superiority to the benchmark dispatching rules when tested on different problem instances with makespan and total weighted tardiness as the objectives. Different aspects of IDRs are also investigated and the insights from these analyses are used to enhance the performance of IDRs.     

Efficient management of production-inventory system in a multi-item manufacturing facility: MTS vs. MTO

Suppliers produce a variety of products to serve both large and small customer orders with unreliable demand information. Furthermore, suppliers also face customer pressure to improve quality, lower cost, and reduce delivery delay. These conflicting objectives lead firms to use both make-to-stock and make-to-order production strategies together. These manufacturing strategies were known to be competing policies and in some cases the choice depends on characteristics of the product. In this study, the firms that manufactured multiple-item types are considered to be free to choose either production policy for each product type (no product-specific requirements are present). Then, using the order-arrival characteristics and cost parameters for each product type, the firm wants to decide which production/scheduling policy to use for each product type. Two production policy (MTS vs MTO) and two scheduling strategy (FIFO vs cyclic) are considered in this study. The analysis and numerical study show that there is no dominant strategy neither for production policy, nor product scheduling policy.     

Make-to-order/make-to-stock partitioning decision using the analytic network process

This paper presents a decision-making structure to determine the appropriate product delivery strategy for different products in a manufacturing system. These strategies include make-to-stock (MTS), make-to-order (MTO), and hybrid MTS/MTO production systems. In fact, the proposed approach gets the decision maker the opportunity to benefit from both strategies through applying the hybrid one. There are varieties of driving factors involved in choosing the right product delivery strategy, and all these factors have positive and negative interactions with each others; in this regard, we apply an appropriate multi-criteria decision-making method. In this method, relevant criteria affecting MTS/MTO partition are split into four categories: market-related criteria, product-related criteria, process-related criteria, and supplier-related criteria. Due to the interdependency between these criteria, we use analytic network process that generalizes analytic hierarchical process by considering the interdependencies among factors. Finally, in order to show the applicability of the proposed structure in practice, the structure is implemented to choose the best production policy among three aforementioned strategies in the real industrial case company.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

Daily stepper scheduling rule in the semiconductor manufacturing for MTO products

The make-to-order (MTO)-type semiconductor manufacturing line may suffer from the complexity of the operational management since the wafer lump corresponding to the specific order can be flown in various patterns, experiencing reentrancy, and complicated product mix. Different from the make-to-stock (MTS)-type memory products, the efficient scheduling policy is not much studied to achieve the demand, meeting related performance measure such as the order fill rate, inventory and shortage, and the cycle time. Because of the computational tediousness, the optimized mathematical programming approach for scheduling is not practical, but the scheduling rule, flexible and fast in computation, is preferred. In this study, the new scheduling priority index, accumulated urgency index (AUI), is developed for the MTO manufacturing line. The urgency index (UI) and balance index (BI) appeared in a literature are compared with AUI to evaluate the performances. It is shown through the computational experiment that AUI outperforms UI and BI in most MTO-related measures and MTS-related ones such as throughput, utilization as well, which are also critical measures even in the MTO manufacturing lines. The experiment is also validated by the ANOVA and Duncan test.     

Dynamic dispatching for interbay material handling by using modified Hungarian algorithm and fuzzy-logic-based control

Semiconductor Wafer Fabrication System (SWFS) is one of the most complicate discrete processing systems in the world. As the wafer size grows from 200 to 300 mm and then to 450 mm in recent years, the interbay automated material handling system (AMHS) has been widely adopted. How to improve the overall efficiency of interbay material handling has therefore become a critical and urgent problem to be solved. However, the large-scale, dynamic and stochastic production environment significantly substantiates the complexity of the scheduling problem. Aiming to meet the demands of adaptive adjusting, efficient scheduling and multiple-objective optimization, a dynamic dispatching method based on modified Hungarian algorithm is proposed. The system parameters, including cassette due date, cassette waiting time, and system load are simultaneously considered, and furthermore the multi-parameters’ weight coefficients are adjusted dynamically by using the fuzzy-logic-based control. Discrete event simulation models are constructed with the eM-Plant software to evaluate the proposed approach. Experimental results show that the proposed dynamic dispatching method improves the system efficiency in terms of mean delivery time, mean waiting time and so on. Meanwhile, the proposed dispatching method has a better comprehensive performance such as the robustness compared to conventional vehicle dispatching approaches.     

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

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

A queuing approach for making decisions about order penetration point in multiechelon supply chains

This study is dedicated to order penetration point (OPP) strategic decision making which is the boundary between make-to-order (MTO) and make-to-stock (MTS) policies. A multiproduct multiechelon production supply chain is considered where the first production stage manufactures semifinished products based on an MTS policy to supply the second production stage which operates on the MTO policy. The producer desires to find the optimal fraction of processing time fulfilled by supplier and optimal semifinished products buffer capacity in OPP. To calculate system performance indexes, the matrix geometric method is employed. Afterward, optimal solutions are obtained by enumeration and direct search techniques. Moreover, the system behavior is analyzed by the numerical example. It is shown that system total cost is a concave function of increasing completed percentage in first production stage. According to the total cost function elements, managers desire to locate OPP where to balance the order fulfillment delay cost, holding cost and the cost of disposing unsuitable items. Finally, the impact of different amounts of storage capacity on OPP and total cost are analyzed. Also, the manner of expected numbers of unsuitable products, semifinished products, and expected order completion delay are analyzed versus various quantities of storage capacity and production rate.     

基于公共缓冲区的柔性流水车间缓冲区动态增容排产方法

实际制造企业通常通过设置公共缓冲区的方法,以此缓解柔性流水车间有限缓冲区容量限制带来的生产堵塞问题,由于公共缓冲区的存在会提高柔性流水车间排产的复杂度,因此提出一种基于模拟退火的类电磁算法(Electromagnetism-like Mechanism algorithm based on Simulated Annealing algorithm,SAEM)与局部调度规则相结合的方法,用以解决这类排产问题。首先建立同时具有有限缓冲区和公共缓冲区的柔性流水车间数学模型;其次由于工件的转运时间代价不能忽略不计,设计局部调度规则来控制工件在生产线上的移动过程,减少转运时间代价对生产过程的影响;最后将引入模拟退火算法思想的类电磁算法作为全局优化算法并与局部调度规则相结合,对同时具有有限缓冲区和公共缓冲区的柔性流水车间进行排产。采用3种不同规模的实例数据进行仿真实验,实验结果表明:在与局部调度规则结合的前提下,SAEM在对优化目标和各评价指标的改善方面均优于标准类电磁(Electromagnetism-like Mechanism,EM)算法和紧致遗传算法(Compact Genetic Algorithm,CGA)。     

An intelligent operations scheduling system in a job shop

Scheduling jobs effectively under the consideration of actual loads on machines is one of the most complicated tasks in production control. The conventional scheduling methods fail because of the complexity of the tasks. To deal with the complexity, knowledge-based approaches to job shop scheduling have been attempted. This paper presents an interactive scheduling expert system, IOSS (Intelligent Operations Scheduling System), which performs both predictive and reactive scheduling. IOSS combines the knowledge-based scheduling method with the interactive scheduling method to generate a feasible schedule and to revise the existing schedule. It is based on opportunistic and interactive repair based problem solving within a blackboard architecture. To handle conflicting events, heuristics are applied from the order point of view. Flexible reaction management is possible while keeping the changes in the generated schedule to a minimum by adjusting the schedule for tardy operations or changes in job shop status. The effectiveness of the proposed concept is demonstrated by applying the developed system to an example case.     

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

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

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.     

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题,提出一种改进的紧致遗传算法（Improved compactgenetic algorithm,ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法,为了克服紧致遗传算法（Compact genetic algorithm,CGA）易早熟收敛的问题,提出一种基于高斯映射的概率模型更新方式,在保持紧致遗传算法快速收敛特性的前提下,扩展了种群中个体的多样性,增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响,设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试,测试结果表明,改进的紧致遗传算法与局部指派规则配合使用,能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。     

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

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

STUDY ON THE DYNAMIC SCHEDULING IN FMS REAL-TIME PRODUCTION ENVIRONMENT

0 INTRODUCTIONThe FMS scheduling task requires scheduling aset of jobs on a finite set of resources according to theproduction plans. In real manufacturing scenario, thedeterministic machine and jOb availability is neverpresent. UnfOreseen situations including machinebreakdowns, and other uncertainties inevitably resultin deviations from the generated ..h.d.l.[l]. Inresponse to changes that take place on shop floor, it isnecessary to revise the existing schedule to improvethe efficiency…     

基于动态阈值神经网络模型的多功能机床Flow Shop排序研究

在生产作用排序中若能充分利用机床功能多样性这一特点,就可有效地缩短零件的总加工时间,提高机床利用率,并使加工系统更具动态应变能力,但机床功能的曾多也使使用排序问题的求解更加复杂和困难,为了降低求解模型的复杂性,这里提出了一种基于动态阈值的神经网络模型与动态调度规则相结合的方法,有于求解面向多功能机床的Flow Shop排序问题。数值实验结果表明了文中方法的有效性。