An immune algorithm approach to the scheduling of a flexible PCB flow shop

Scheduling is an important task in manufacturing. It involves assigning jobs to machines in a particular order so as to meet the manufacturing target. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA), which is a new evolutionary algorithm, can be used to tackle complex scheduling problems and produce a reasonable manufacturing schedule within an acceptable time. This paper describes an IA approach to the scheduling of a flexible flow shop for PCB manufacturing. An overview of the flexible flow shop problem and the basic notions of an IA are first presented. Subsequently, the details of an IA approach are described and implemented. A case study of a flexible flow shop for the manufacture of PCBs for communication equipment was then conducted. The results obtained are compared with those computed by genetic algorithms (GAs), which are well-known evolutionary algorithms. From the case study, it was established that IAs outperformed GAs. The details of the case study as well as the comparative study are described.     

Solving manpower scheduling problem in manufacturing using mixed-integer programming with a two-stage heuristic algorithm

Manpower scheduling problem is one of the key scheduling problems with extensive applications in manufacturing. This paper presents a mixed-integer programming model with a two-stage heuristic algorithm for solving the manpower scheduling problem in the precision engineering industry. Firstly, a mixed-integer programming formulation is developed to model the manpower scheduling problem in this high-mix low-volume manufacturing environment. Secondly, a two-stage heuristic algorithm is proposed where the first stage is deployed to calculate the skill requirements for each shift by considering the jobs, machines, and their production schedule and the second stage is designed to assign operators to the machines by considering the skill set requirements and the operator's expressed preferences. Lastly, the computational results based on problem instances emulating real-world scenarios demonstrated the feasibility and effectiveness of the proposed heuristic.     

Dynamic production planning model: a dynamic programming approach

Production planning is one of the most important issues in manufacturing. The nature of this problem is complex and therefore researchers have studied it under several and different assumptions. In this paper, applied production planning problem is studied in a general manner and it is assumed that there exists an optimal control problem that its production planning strategy is a digital controller and must be optimized. Since this is a random problem because of stochastic values of sales in future, it is modeled as a stochastic dynamic programming and then it is transformed to a linear programming model using successive approximations. Then, it is proved that these two models are equivalent. The main objective of the proposed model is achieving optimal decisions using forecasting sales which can be applied in master production schedule, manufacturing resource planning, capacity requirements planning, and job shop/shop floor scheduling.     

动态制造环境下的可变特征制造系统自适应调度方法研究

针对动态环境下的可变特征制造系统自适应调度问题,提出了基于合弄体的自治与协调机制,将复杂制造系统的制造资源分解为若干个自治的子合弄体,通过组织不同的子合弄体构建了基于生产任务的可变特征制造系统.由于瓶颈工位的子合弄被多个生产任务共同使用,采用基于瓶颈的启发式算法对瓶颈子合弄进行调度排序,从而实现了动态环境下的可变特征制造系统自适应调度.最后给出了系统应用效果,运行结果表明所提出的方法是有效的.     

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.     

Developing manufacturing control software: A survey and critique

The complexity and diversity of manufacturing software and the need to adapt this software to the frequent changes in the production requirements necessitate the use of a systematic approach to developing this software. The software life-cycle model (Royce, 1970) that consists of specifying the requirements of a software system, designing, implementing, testing, and evolving this software can be followed when developing large portions of manufacturing software. However, the presence of hardware devices in these systems and the high costs of acquiring and operating hardware devices further complicate the manufacturing software development process and require that the functionality of this software be extended to incorporate simulation and prototyping.This paper reviews recent methods for planning, scheduling, simulating, and monitoring the operation of manufacturing systems. A synopsis of the approaches to designing and implementing the real-time control software of these systems is presented. It is concluded that current methodologies support, in a very restricted sense, these planning, scheduling, and monitoring activities, and that enhanced performance can be achieved via an integrated approach.     

A Prototype Genetic Algorithm-Enhanced Multi-Objective Scheduler for Manufacturing Systems

This paper describes the development of a prototype genetic algorithm-enhanced multi-objective scheduler for manufacturing systems. A framework of the prototype scheduler is proposed which accepts data input from a database or file and outputs a near-optimal schedule. A scheduling toolbox with scheduling models for job shop, flow shop and cellular manufacturing, forms part of the prototype scheduler, and the schedule builder transforms the near-optimal solution into a valid shop floor schedule. The prototype system was validated for various cases, with and without constraints and multiple objective functions, (makespan and tardiness), enforced simultaneously with constraints. In the first case, the schedule generated was comparable to those obtained by other researchers. The prototype system was also tested for its ability to handle dynamic scheduling, e.g. a rush order. The results showed that all the job orders could be rescheduled within the original makespan, even though the order of one of the jobs was doubled.     

A study on the weighted composite dispatching rule in modular production systems

Scheduling semi-conductor manufacturing process systems is a complicated and difficult job, due to such characteristics as re-entry into manufacturing processes, high uncertainty of processes, and products and technologies changing rapidly. The researchers have carried out many studies to find efficient techniques for semi-conductor manufacturing systems with a view to accomplishing the goals of systems, such as saving cycling time and increasing production quantity per unit time. The production flow in the semi-conductor industry has the most unique characteristics, which makes it difficult to plan production and to schedule semi-conductor manufacturing. Currently, the scheduling methods in semi-conductor assembly processes follow the dispatching rule on a simple first come first serve (FCFS) basis, and a backlog is operated as a buffer based on the daily production quantity. In this study, therefore, we will apply various dispatching rules on a real-time basis and verify the effect and result of exact scheduling through simulation, based on the assumption that competitive advantages in production come from efficient inventory control and exact scheduling.     

客户竞争驱动的任务调度非合作博弈

从客户竞争需求的角度出发,在分析其提交制造任务的各自利润最大化(重点考虑任务的完成时间)调度目标的基础上,针对传统的任务调度策略、方法和模型的不足,采用博弈论,提出并构建了一种具备完全信息的非合作博弈的任务调度模型。在该任务调度模型中,来源于不同客户的制造任务被映射为博弈模型中的局中人,与各制造任务所包含的工序集对应的可选加工设备被映射为各制造任务的可行方案集,各制造任务加工完成时间的倒数被映射为其收益函数。据此,对上述任务调度目标的求解就等价为寻求该任务调度模型的Nash均衡点,对Nash均衡点的具体求解,采用遗传算法实现。最后给出具体的实例来验证其可行性。     

Efficient dispatching rules for dynamic job shop scheduling

This study attempts to provide efficient dispatching rules for dynamic job shop scheduling by combining different dispatching rules. A dispatching rule is used to select the next job to be processed from a set of jobs awaiting service. A job shop will be treated as dynamic, when conditions such as continuously arriving new jobs and deviations from current schedule need to be accommodated, and a job shop should be treated as an integrated part of a manufacturing system. The discussion includes a simulation technique which uses ARENA 4.0. software to simulate the dynamic model of a job shop under various rules and performance measures . Results of the simulation show that, for most of the performance measures, combined rules perform well. In this study, the combined rules MWKR_FIFO and TWKR_SPT do well under most conditions.     

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.     

一种可重构制造系统的生产计划方法

虚拟企业是实现敏捷制造的有效途径，是一种可重构的制造系统。系统在重构过程中，各合作伙伴给出完成各自任务的时间段，制造系统则基于这些信息编排出生产计划。本文建立了这一生产计划问题的数学模型，基于该模型，提出了一个有效算法，并给出了一个简单算例。结果表明，所提出的算法可以决定解的存在性，如果解存在，则求出有效解；如果解不存在或解不可以接受，盟主可与合作伙伴协商解决问题。     

Multi-agent-based proactive–reactive scheduling for a job shop

Multi-agent-based proactive–reactive scheduling for job shops is presented, aiming to hedge against the uncertainties of dynamic manufacturing environments. This scheduling mechanism consists of two stages, including proactive scheduling stage and reactive scheduling stage. In the proactive scheduling stage, the objective is to generate a robust predictive schedule against known uncertainties; in the reactive scheduling stage, the objective is to dynamically rectify the predictive schedule to adapt to unknown uncertainties, viz. the reactive scheduling stage is actually complementary to the proactive scheduling stage. A stochastic model is presented, which concerns uncertain processing times in proactive scheduling stage on the basis of analyzing the deficiencies of a classical scheduling model for a production schedule in practice. For the stochastic scheduling problem, a multi-agent-based architecture is proposed and a distributed scheduling algorithm is used to solve this stochastic problem. Finally, the repair strategies are introduced to maintain the original proactive schedule when unexpected events occur. Case study examples show that this scheduling mechanism generates more robust schedules than the classical scheduling mechanism.     

Control theoretic model using PID controller for just-in-time production scheduling

Today, manufacturing companies are under the pressure to reduce the variations in product delivery to customers with minimized manufacturing costs. In this circumstance, the job completions are required to be as close to due dates, which can be the objective of just-in-time (JIT) production. Thus, this paper proposes an innovative approach using a feedback controller for JIT production scheduling. Specifically, a feedback control system using proportional, integral, and derivative (PID) controller is designed to control the trajectory of arrival times in a single machine configuration, based on which various schedules are generated. Importantly, control system gains (proportional, integral, and derivative) are synthesized to generate an optimal or close to the optimal schedule in terms of due-date deviations and system stability. More specifically, control system gains are trained using the problem sets with known optimal schedules, and these trained gains are tested. It is expected that the proposed PID controller can be effectively applied for scheduling and rescheduling under various disturbances that cause destabilization of the system.     

Selection of scheduling rules in FMSs—A simulation approach

This paper deals with the development of a microcomputer-based simulation model of a random flexible manufacturing system aimed at solving scheduling problems. The model is written in SLAM II and can be used interactively. It offers five alternative scheduling rules, but other rules could be incorporated if required. The selection process is demonstrated through an example, and an experimental design is conducted to evaluate the effect of changes in the levels of various resources on system performance.     

工件加工随机调度中优先约束问题的研究

讨论工件加工时间为任意随机分布的随机变量的单机随机调度问题,设工件间的约束为树优先约束,目标函数为极小化加权完工时间和的数学期望.这一模型在机械设计与制造行业中的多个元器组件加工,以及钢铁板坯轧制等众多实际生产制造领域中都具有广泛的应用背景.证明了工件加工时间为任意随机分布的随机变量的情况下,最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的调度为最优调度,给出了最优多项式算法,该算法可以被推广应用于实际的生产中,具有较强的实际应用性.     

基于仿真的车间作业计划系统研究

基于仿真的车间作业计划系统可以增加系统的透明度,提高计划执行率.针对多品种小批量的生产模式,在eM-Plant软件上提出一种基于离散事件的仿真方案,开发了相应的系统模型和仿真算法,运行仿真系统,得到调度结果,验证所编制的车间计划的可行性.采用上述仿真系统就某军工车间一计划周期的生产任务进行仿真,根据不同优先级的仿真算法,得到合理的车间作业计划.实例证明本系统提高了车间作业计划编制有效性.     

Dynamic rescheduling in FMS that is simultaneously considering energy consumption and schedule efficiency

The dynamic rescheduling problem in flexible manufacturing systems (FMS) has historically emphasized the schedule efficiency. However, energy consumption is a basic need for different purposes in manufacturing systems around the world. This paper proposes an innovative approach to study the dynamic scheduling problem in FMS, taking the objectives of minimum or maximum energy consumption into account. A new goal programming mathematical model, which considers the energy consumption and the schedule efficiency simultaneously, is presented for solving this problem. A rescheduling method based on the genetic algorithm is introduced to address the dynamic rescheduling problem in FMS. A period policy is selected to deal with the dynamic feature of the problem. Numerical experiments have been designed to test and evaluate the performance of the proposed model. The experimental results show that the minimum energy consumption model can save the energy consumption and enhance the schedule efficiency.     

An intelligent concurrent design task planner for manufacturing systems

Product design is an integral component of manufacturing systems. This paper presents a prototype intelligent concurrent design task planner, which combines the strength of genetic algorithms and an iterative design analyser for the scheduling of a complex design process of a manufacturing system. It accounts significantly for shortening the time-to-market of a product, and hence, improves the agility of a manufacturing system. The proposed prototype attempts to schedule the design process inherently containing iteration, which is caused by the interdependencies among tasks and leads to prolonged lead-time and increased cost on the whole time-span of introducing a product. Genetic algorithm (GA), as one of the effective optimisation techniques, is embodied in the prototype to search for the optimal schedule for a design process for the goal of satisfying the managerial objective under resource constraints. The iterative design analyser, which is basically an analytical tool for design iteration, is utilised to estimate the time and engineering cost spent on the design process for each candidate schedule. Considering the unpredictable length of a schedule for iterative design process, a novel chromosome representation scheme and unique crossover and mutation operators have been introduced. A case study conducted on a burn-in system of a manufacturing company has illustrated the effectiveness of the proposed prototype.     

A game-theory approach for job scheduling in networked manufacturing

This paper presents a new kind of scheduling solution for jobs in networked manufacturing environments. The main contributions of this study can be focused on three points: The first is to distinguish the concepts and requirements of job scheduling in the networked manufacturing environment form those in the traditional manufacturing environment. The second is to construct a game-theory mathematical model to deal with this new job scheduling problem. In this presented mathematical model, this new job scheduling problem is formulated as an N-person non-cooperative game with complete information. The players correspond to the jobs submitted, respectively, by related customers and the payoff of each job is defined as its makespan. Each player has a set of strategies which correspond to the feasible geographical distributive machines. Therefore, obtaining the optimal scheduling results is determined by the Nash equilibrium (NE) point of this game. In order to find the NE point, the last point is to design and develop a genetic algorithm (GA)-based solution algorithm to effectively solve this mathematical model. Finally, a numerical example is presented to demonstrate the feasibility of the approach.