Real-Time Manipulation of Alternative Routeings in Flexible Manufacturing Systems: A Simulation Study

This paper presents the results of a simulation study of a typical flexible manufacturing system (FMS) that has routeing flexibility. The objective is this study is to test the effectiveness of the dissimilarity maximisation method (DMM) for real-time FMS scheduling. DMM is an alternative process plan selection method developed for routeing selection in off-line FMS sched-uling. An integrated framework that consists of a computer simulation model, which mimics a physical system, a C++ module, and a linear program solver is used to evaluate the effects of various operational control rules on the system performance. The hypothetical FMS employed in this study consists of seven machining centres, a loading and an unloading area, and six different part types. Owing to the existence of identical machining centres in the system, the part types have alternative routeings. For selecting an incoming part and later routeing it to a machining centre for its next operation, three control rules, namely, first-in first-out/first available (FIFO/FA), equal probability loading (EPL), and dissimilarity maximisation method/first-in first-out (DMM/ FIFO) are used. In this study, DMM is 1. Used as a real-time decision-making tool to select routeings for the parts that are in the system. 2. Tested and benchmarked against FIFO/FA and EPL. The results show that DMM/FIFO outperforms FIFO/FA and EPL on system throughput. Other measures such as average waiting time, average transportation time, and percentage utilisation rates are also investigated to provide insights for the effectiveness of the DMM rule for real-time FMS control applications.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Input sequencing and scheduling for a reconfigurable manufacturing system with a limited number of fixtures

We consider the input sequencing and scheduling problems in a reconfigurable manufacturing system, a state-of-the-art manufacturing system designed at the outset for rapid changes in its hardware and software components. Due to the inherent operation and routing flexibilities of the system, each part is processed according to a multiple process plan, i.e., each part can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) the sequence of parts to be released into the system; (b) the selection of operation/machine pair; and (c) the sequence of the parts assigned to each machine within the system. In particular, we consider the practical constraint that the number of fixtures is limited and hence a part can be released into the system only when the fixture required for the part is available. To solve the integrated input sequencing and scheduling problems, we suggest a practical priority rule based approach in which the three decisions are done using a combination of dispatching rules, i.e., those for input sequencing, operation/machine selection, and part sequencing. To show the performances of various rule combinations, simulation experiments were done on the data derived from a real system, and the test results are reported.     

Real-time rescheduling metaheuristic algorithms applied to FMS with routing flexibility

This paper presents the results of a simulation study of a typical flexible manufacturing system that consists of seven machining centres, a loading and an unloading area, and six different part types. Owing to the existence of identical machining centres, the part types have alternative routings (their number varies between two and eight). One of the objectives of this work is to show how the following metaheuristics: ant colony optimisation, genetic algorithms, simulated annealing, tabu search, particle swarm optimisation and electromagnetism-like method, are adapted for solving the alternative routing selection problem in real time in order to reduce the congestion in the system by selecting a routing for each part among its alternative routings. The other goal is to highlight the impact of the real-time rescheduling of parts contained in the loading station on system performances when these metaheuristics are applied. The simulation results jugged by the production rate, machines and material handling utilisation rate show that for an overloaded system, the real-time rescheduling outperforms the case without rescheduling, but it has a negative impact on the work in process.     

A heuristic algorithm for cell formation problems with consideration of multiple production factors

For the design of manufacturing cells, numerous mathematical models and various algorithms have been extensively investigated in the literature. However, most of the proposed models and algorithms have more or fewer drawbacks on the issues with real-life situations. In this paper, we propose a mathematical model that incorporates multiple key real-life production factors simultaneously, namely, production volume, batch size, alternative process routings and perfect coefficient of each routing, cell size, unit cost of intercell/intracell movements, and path coefficient of material flows. Then, to solve this NP-hard model, we develop a heuristic algorithm with three stages: (1) form the temporary machine group plan according to the alternative process routings of each part, (2) select the appropriate process routing of each part with respect to the over-all material movement cost, and (3) configure the regular manufacturing cells based on the appropriate process routing. A simple numerical example and an industrial case are used to test the computational performance of the proposed algorithm. The test results imply that it is useful for manufacturing cell design in both quality and speed.     

Workload balance and part-transfer minimization in flexible manufacturing systems

Problems related to the flow management of a flexible manufacturing system (FMS) are here formulated in terms of combinatorial optimization. We consider a system consisting of several multitool automated machines, each one equipped with a possibly different tool set and linked to each other by a transportation system for part moving. The system operates with a given production mix.The focused flow-management problem is that of finding the part routings allowing for an optimal machine workload balancing. The problem is formulated in terms of a particular capacity assignment problem.With the proposed approach, a balanced solution can be achieved by routing parts on a limited number of different paths. Such a balancing routing can be found in polynomial time. We also give polynomial-time and-space algorithms for choosing, among all workload-balancing routings, the ones that minimize the global amount of part transfer among all machines.     

具有机器学习能力的智能车间调度系统

本文从制造领域发展趋势的角度出发，阐述优化设计车间调度系统的必要性，进而介绍一种具有机器学习能力的智能车间调度系统的设计     

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.     

A machine cell formation algorithm for simultaneously minimising machine workload imbalances and inter-cell part movements

This paper considers a multi-objective machine cell problem, in which part types have several alternative part routings and the expected annual demand of each part type is known. This problem is characterised as optimally determining part type (routing) sets and corresponding machine cells such that total inter-cell part movements and total machine workload imbalances are simultaneously minimised. Due to the complexity of the problem, a two-stage heuristic algorithm is proposed, and computational experiments were conducted to verify the performance of the algorithm.     

Integrating Flexible Process Plans with Scheduling in Flexible Manufacturing Systems

This paper highlights the importance of integration between process planning and scheduling in flexible manufacturing systems (FMS). An effective integration increases the potential for enhanced system performance and enhanced decision making A framework that integrates flexible process plans with off-line (predictive) scheduling in FMS is presented. The flexibility in process planning, including process flexibility, sequence flexibility, and alternative machine tools, is discussed. The proposed framework consists of four integrated stages with the objective of reducing the completion time. The integrated stages include: 1. Machine tool selection. 2. Process plan selection. 3. Scheduling. 4. Re-scheduling modules. In addition, the paper proposes a new approach, namely the Dissimilarity Maximisation Method (DMM), for selecting the appropriate process plans for a part mix where parts have alternative process plans. The recursive structure of the framework provides a different approach, namely overlapping schedules, which considers a longer scheduling period as comprising several short scheduling periods. Knowing that neither the process plans nor the planned (predicted) schedules are truly followed on the shop floor, the related literature and the corresponding approaches are compared in order to envisage new approaches for closing the gap between process planning and scheduling.     

An adaptive approach to dynamic scheduling in knowledgeable manufacturing cell

To overcome deficiency in the global capacity of a single dispatching rule, it is vital to select a dispatching rule in real time for dynamic scheduling. Among the studies addressing the method for selecting dispatching rules, few have no requirements for domain knowledge or accurate training example, which is hard to acquire from the real production system. In this paper, a new learning algorithm, along with the presentation of an adaptive scheduling control policy, is proposed to obtain the dynamic scheduling knowledge effectively, and different dispatching rules are selected to schedule the jobs in the machine buffer according to the current transient state of the system. Case studies are given to illustrate the validity of the scheduling control policy.     

Single machine scheduling with multiple objectives in semiconductor manufacturing

To deal with today’s stiff competition in the logistics of semiconductor manufacturing, the development of an efficient scheduling approach for the complex semiconductor back-end testing operations is very essential, where more than one objective, such as cycle time, machine utilization and due date accuracy are kept in the focus to various degrees simultaneously. In this paper, the problem of scheduling N independent jobs on a single testing machine with due dates and sequence-dependent setup times is addressed, where the multiple objectives are to minimize average cycle time and average tardiness and to maximize machine utilization. A near optimal solution, which is not inferior to any other feasible solution in terms of all objectives, is generated combining the analytically optimal and conjunctive simulated scheduling approach. First, the machine-scheduling problem is modeled using the discrete event simulation approach and the problem is divided into simulation clock-based lot selection sub-problems. Then, at each decision instance in simulated time, a Pareto optimal lot is selected using the compromise programming technique for multi-objective optimization. With the help of a broad experimental design, this developed solution is then compared with common heuristic-dispatching rules used in industry such as the shortest processing time (SPT) and earliest due date (EDD). The developed scheduling method shows better results for all the objectives over a wide range of problems. It shows approximately 16.7% reduction in average cycle time, 25.6% reduction in average tardiness, and 21.6% improvement in machine utilization over the common dispatching rules, SPT and EDD.     

考虑设备维修与维护的装配作业车间动态生产仿真研究

装配作业车间生产调度的关键是动态协同产品各零件的生产进度以满足产品的齐套需求。设备的随机故障将会扰乱已有的生产计划,给各零件之间的进度协同带来更高的挑战。预防性维护能够提高设备的可靠度以减少故障的发生,但过度的维护又会减少生产加工的时间。从调度规则构成属性的角度分析设备故障将带来的影响,并提出一种考虑设备故障的改进型调度规则。通过仿真试验分析了企业常见的3种预防性维护策略对车间性能的影响和7种代表性调度规则的性能。试验结果表明:预防性维护策略对车间有明显的影响;且考虑了设备故障的调度规则有一定的改进效果。     

A genetic algorithm based cell design considering alternative routing

This paper describes a method for simultaneous arrangement of part families and machine cells for cellular manufacturing systems. A unique feature of the proposed method is that it takes into account the relevant production data such as production volume, alternate routings and process sequences. It also has the ability to select the best alternative routing in terms of cell formation for each part before attempting to cluster the machines and the parts. The formation of the part families and the machine cells has been treated as a minimization problem according to a defined cost function. A genetic algorithm is then developed for solving the minimization problem. Two examples are presented to illustrate the usefulness of the proposed method. The strength of this method lies behind its independence from initial conditions and type of objective function.     

Development and evaluation of feature-focused dynamic routing policy

This paper reports on a development of feature-focused dynamic routing policy and its evaluation in a flexible manufacturing systems (FMS) simulation framework. The dynamic policy is based on an integrative methodology in which process planning system IMPlanner is integrated with FMS simulation module. IMPlanner’s rule-based system process selection system performs knowledge-intensive task of generating alternative processing options for each feature for parts in production plan. Generated alternative routings (process plan network) for each part are utilized in the FMS simulation module such that routing decision in FMS are made on periodic intervals by considering alternative processes for each feature and making decision based on the current system status and performance. The proposed framework has been evaluated in an experimental FMS simulation module, implemented in Arena, in which two performance criteria, machine utilization and WIP, were used to make routing decisions. The feature-focused approach is compared with traditional static decision-making, and its improved performance is demonstrated.     

Makespan minimization for m-machine permutation flowshop scheduling problem with learning considerations

Increased complexity of current manufacturing systems together with dynamic conditions and permanent demands for flexible and robust functionality makes their management and control very difficult and challenging. Workflow simulation is an effective approach to investigate dynamic workflow scheduling policies and evaluate the overall manufacturing system performance. The results attained in simulation model can give directions on how to maximize system output when selecting an appropriate scheduling practice for a real system. In this paper, we investigate the abilities of multi-agent systems in combination with dynamic dispatching rules and failure handling mechanisms to manage dynamic environment conditions (such as machine failures) for systems in the production automation domain. We measure system robustness by systematically assessing the total system performance (e.g., number of finished products) in a number of representative test cases. We use an agent-based simulation environment, MAST, which has been validated with real-world hardware to strengthen the external validity of the simulation results. We investigated the performance of a re-scheduling component which uses four different policies that define how to adjust the system schedule in case of machine disturbances/failures. In the context of the empirical study the Complete Rerouting re-scheduling policy outperformed all other policies.     

Effects of routing flexibility, sequencing flexibility and scheduling decision rules on the performance of a flexible manufacturing system

This paper focuses on a simulation-based experimental study of the interaction among routing flexibility, sequencing flexibility and part sequencing rules in a typical flexible manufacturing system (FMS). Two scenarios are considered for experimentation. Three routing flexibility levels, five sequencing flexibility levels and four scheduling rules for part sequencing decision are considered for detailed investigation. The performance of the FMS is evaluated using various measures related to flow time and tardiness of parts. The simulation results are subjected to statistical analysis. The analysis of results reveals that deterioration in system performance can be minimized substantially by incorporating either routing flexibility or sequencing flexibility or both. However, the benefits of either of these flexibilities diminish at higher flexibility levels. Part sequencing rules such as earliest due date and earliest operation due date provide better performance for all the measures at higher flexibility levels.     

模拟退火粒子群优化算法在工艺规划决策中的应用

为了实现面向精益生产的制造系统中的工艺与调度并行设计,在工艺规划决策中,建立了面向精益生产的工艺规划与调度集成模型.在考虑设备负载平衡以及完成加工任务时间最短的条件下,设计了一种离散模拟退火粒子群优化(Particle Swarm Optimization based on Simulated Annealing,SAPSO)算法,并行设计及优化零件的工艺方案和调度方案,并最终获得其最优工艺方案及与之相对应的优化调度方案.通过对10台设备10种零件的示例仿真验证了算法的有效性.     

A comparative study of FMS tool allocation and part type selection approaches for a varying part type mix

Hankins and Rovito (1984) examined the impact of different tool policies on cutting tool inventory levels and spindle utilization for a flexible manufacturing system (FMS). This study provides a broader perspective of the impact of tool allocation approaches on flow times, tardiness, percent of orders tardy, machine utilization, and robot utilization. Part type selection procedures have been suggested for the FMS prerelease planning problem. However, very little research has specifically evaluated the part type selection procedures across different tool allocation approaches. Also, with the exception of Stecke and Kim (1988, 1991) no other known study has provided any insights on what tool allocation approaches are appropriate when processing different mixes of part types. This research is devoted to addressing those issues.Three tool allocation approaches, three production scheduling rules, and three levels of part mix are evaluated in this study through a similation model of a flexible manufacturing system. The specific impacts of the tool approaches, their interaction effects with the part type selection rules, and their effectiveness at different part type mix levels are provided through the use of a regression metamodel.     

Multicriteria dynamic scheduling by swapping of dispatching rules

For most shop floors, consideration of more than one criterion would be likely to provide more realistic scheduling of a given set of jobs. The present paper considers this aspect of scheduling and uses an algorithm proposed by the authors in their previous work for implementing several criteria simultaneously in a shop of dynamic nature. The algorithm considers several dispatching rules simultaneously for selecting a job for processing and continuously monitors the attained values of performance measures. The selection of dispatching rules is made by identifying the worst performing criterion. A rule that can improve system performance for the worst-performing criterion is selected to dispatch the part under consideration. In this paper, several case studies have been attempted to evaluate the efficiency of the algorithm. The results of the taken case studies indicate that in a dynamic system the system performance improves by changing the dispatching rules corresponding to the worst-performance criterion at the appropriate deterioration in the performance measures.