A genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

Anticipation and flexibility in dynamic scheduling

Many real-world optimization problems change over time and require frequent re-optimization. We suggest that in such environments, an optimization algorithm should reflect the problem's dynamics and explicitly take into account that changes to the current solution are to be expected. We claim that this can be achieved by having the optimization algorithm search for solutions that are not only good, but also flexible, i.e. easily adjustable if necessary in the case of problem changes. For the example of a job-shop with jobs arriving non-deterministically over time, we demonstrate that avoiding early idle times increases flexibility, and thus that the incorporation of an early idle time penalty as secondary objective into the scheduling algorithm can greatly enhance the overall system performance.     

Performance-based dynamic scheduling model for flexible manufacturing systems

A performance-based dynamic scheduling model for random flexible manufacturing systems (FMSs) is presented. The model is built on the mathematical background of supervisory control theory of discrete event systems. The dynamic FMS scheduling is based on the optimization of desired performance measures. A control theory-based system representation is coupled with a goal programming-based multi-criteria dynamic scheduling algorithm. An effectiveness function, representing a performance index, is formulated to enumerate the possible outputs of future schedules. Short-term job scheduling and dispatching decisions are made based on the values obtained by optimizing the effectiveness function. Preventive actions are taken to reduce the difference between actual and desired target values. To analyse the real-time performance of the proposed model, a software environment that included various Visual Basic Application® modules, simulation package Arena®, and Microsoft Access® database was developed. The experimentation was conducted (a) to determine the optimum look-ahead horizons for the proposed model and (b) to compare the model with conventional scheduling decision rules. The results showed that the proposed model outperformed well-known priority rules for most of the common performance measures.     

Dynamic scheduling for complex engineer-to-order products

The current paper considers dynamic production scheduling for manufacturing systems producing products with deep and complex product structures and complicated process routings. It is assumed that manufacturing and assembly processing times are deterministic. Dynamic scheduling problems may be either incremental (where the schedule for incoming orders does not affect the schedule for existing orders) or regenerative (where a new schedule is produced for both new and existing orders). In both situations, a common objective is to minimize total costs (the sum of work-in-progress holding costs, product earliness and tardiness costs). In this research, heuristic and evolutionary-strategy-based methods have been developed to solve incremental and regenerative scheduling problems. Case studies using industrial data from a company that produces complex products in low volume demonstrate the effectiveness of the methods. Evolution strategy (ES) provides better results than the heuristic method, but this is at the expense of significantly longer computation times. It was found that performing regenerative planning is better than incremental planning when there is high interaction between the new orders and the existing orders.     

Setup tasks scheduling during production resettings

Production waste reduction during production resettings is critical in the industry as it is the key point of flexibility increase. One way to improve production waste is to assign setup tasks efficiently to operators. This article describes a possible model of this problem adapted to a real-life application. This model is based on an unrelated parallel machines problem that takes into consideration the skills of the operators and the production line structure. The nature of the data and some industrial constraints help us simplifying this problem into an assignment problem. As often in the industry, the objective is to maximise production. Because most production lines are complex series parallel lines, it is often possible to maintain production even if not all machines are running. This particularity makes the criterion hard to express as it depends on the line structure. In this article we describe three heuristics to solve this problem: a hill climbing algorithm, a genetic algorithm and a memetic algorithm that combines the advantages of the two previous algorithms. The neighbourhood used for these algorithms is based on multiple exchanges of tasks between operators.     

分布式实时系统任务调度算法的设计和实现

针对分布式实时任务中容易引起的任务分配不合理及系统负载不平衡的情况,根据分布式实时任务多机执行的特点及分布式实时系统在同一结点上有多任务执行,提出了两级分布式系统结构下实时任务的调度策略：任务分配和任务调度。实验表明,在任务分配阶段提出的算法可以更合理地平衡任务,在任务调度阶段采用的调度算法能够更好地完成任务的执行。     

Electroplating production scheduling by cyclogram unfolding in dynamic hoist scheduling problem

This article presents a scheduling problem that exists in electroplating lines. An electroplating line is an automated manufacturing system which covers machine parts with a coat of metal. It consists of a set of tanks that chemically process the items and hoists that transport the items between workstations. Scheduling the movements of these hoists is commonly called a hoist scheduling problem. The most common approaches to the problem are cyclic hoist scheduling problem and dynamic hoist scheduling problem (DHSP). This article presents a DHSP solution method. The method divides the problem into real time and non-real time. Special schedules, called cyclograms, allow minimisation of the length of non-real time calculations. A notion of the problem is introduced, an outline of a scheduling system is presented, as well as the heuristic algorithm itself. The results of the described method, referred to as a cyclogram unfolding method, are compared to several cases available in the literature.     

Minimising earliness and tardiness by integrating production scheduling with shipping information

Minimisation of earliness and tardiness is known to be critical to manufacturing companies because it may induce numerous tangible and intangible problems, i.e. extra storage cost, spacing, risk of damages, penalty, etc. In literature, earliness and tardiness is usually determined based on order due date, generally regarded as the time of delivering the finished products to the customers. In many papers, delivery time and cost required are usually simplified during the production scheduling. They usually assume that transportation is always available and unlimited. However, transportation usually constructs a critical portion of the total lead time and total cost in practice. Ignoring that will lead to an unreliable schedule. This is especially significant for electronic household appliances manufacturing companies as the studied company in this paper. In general, they usually rely on sea-freight transportation because of the economic reasons. As different sea-freight forwarders have different shipments to the same destination but with different shipping lead time, cost and available time. Adequately considering this shipping information with the production scheduling as an integrated model can minimise the costs induced by earliness and tardiness and the reliability of the schedule planned. In this paper, a two-level genetic algorithm (TLGA) is proposed, which is capable of simultaneously determining production schedule with shipping information. The optimisation reliability of the proposed TLGA is tested by comparing with a simple genetic algorithm. The results indicated that the proposed TLGA can obtain a better solution with lesser number of evolutions. In addition, a number of numerical experiments are carried out. The results demonstrate that the proposed integrated approach can reduce the tardiness, the storage cost, and shipping cost.     

Agent-based distributed scheduling for virtual job shops

Nowadays, market globalisation and stiff world-wide competition require flexible, demand-driven, and reconfigurable production systems that can adapt to the requirements of the increasing reduction in product life cycle and rapid changes in market demand. The advent and development of network technology (especially the Internet) and distributed computing technology make it possible for geographically dispersed manufacturing resources to be integrated and deployed effectively and efficiently. In addition, manufacturing enterprises can expand their throughput within a short time and rapidly reduce the production cycle via transferring certain jobs to other available manufacturing resources in the globalised manufacturing environment, viz., manufacturing enterprises can expand their throughput through the dynamic formation of virtual job shops according to the production requirements. Owing to more open manufacturing environments and rapid changes of market demands, the traditional centralised scheduling approaches are not suitable for this open distributed manufacturing environment. This paper proposes a distributed scheduling approach in which a multi-agent solution towards a ‘task-machine’ assignment is presented. The main points of discussion are the formation of a virtual job shop that is based on market mechanism and the distributed scheduling approach based on negotiation.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

Mitigating supply and production uncertainties with dynamic scheduling using real-time transport information

Supply and production uncertainties can affect the scheduling and inventory performance of final production systems. Facing such uncertainties, production managers normally choose to maintain the original production schedule, or follow the first-in-first-out policy. This paper develops a new, dynamic algorithm policy that considers scheduling and inventory problems, by taking advantage of real-time shipping information enabled by today’s advanced technology. Simulation models based on the industrial example of a chemical company and the Taguchi’s method are used to test these three policies under 81 experiments with varying supply and production lead times and uncertainties. Simulation results show that the proposed dynamic algorithm outperforms the other two policies for supply chain cost. Results from Taguchi’s method show that companies should focus their long-term effort on the reduction of supply lead times, which positively affects the mitigation of supply uncertainty.     

Alternative control mechanisms for cyclical scheduling systems

This paper investigates the relative performance of alternative mechanisms for controlling the cycle length in a cyclical scheduling system. While all methods investigated are able to maintain a target long run average cycle length, some provide greater inventory efficiency than others, with more informed application of idle time. Simulation results demonstrate that a fixed idle time policy provides worst results, while an aggregate workload heuristic based on earlier dynamic policy characterisation provides superior performance. The importance of the control mechanism is shown to be greatest when the process is subject to high demand intensity, particularly when the demand process is sporadic.     

The equipment maintenance scheduling problem in a coal production system

This paper addresses an equipment maintenance scheduling problem in a coal production system which includes three consecutive stages: the coal mining stage, the coal washing stage and the coal loading stage. Each stage is composed of different equipment that needs maintenance each day. There exists intermediate storage with finite capacities and the finished products are transported by train. Moreover, some equipment has a different preference for (aversion to) the start time of maintenance (STOM). The objective is to minimise the weighted sum of aversion about STOM, changeover times and train waiting time. We first formulate this problem into a mixed integer linear programming (MILP) model, then a hybrid genetic algorithm (HGA) is proposed to solve it. The proposed method has been tested on a practical coal enterprise in China and some randomly generated instances. Computational results indicate that our algorithm can produce near-optimal solutions efficiently.     

Divergent production scheduling with multi-process routes and common inventory

This research considers a scheduling problem in a divergent production system (DPS) where a single input item is converted into multiple output items. Therefore, the number of finished products is much larger than the number of input items. This paper addresses two important challenges in a real-life DPS problem faced by an aluminium manufacturing company. One challenge is that one product can be produced following different process routes that may have slightly different capabilities and capacities. The other is that the total inventory capacity is very limited in the company in the sense that a fixed number of inventory spaces are commonly shared by raw materials, WIP (work-in-process) items and finished products. This paper proposes a two-step approach to solving this problem. In the first step, an integer programming (IP) model is developed to plan the type and quantity of operations. In the second step, a particle swarm optimisation (PSO) is proposed to schedule the operations determined in the first step. The computational results based on actual production data have shown that the proposed two-step solution is appropriate and advantageous for the DPS scheduling problem in the company.     

Optimising lot sizing and order scheduling with non-linear production rates

This research focuses on developing an optimum production schedule in a process with a non-linear production rate. Non-linear production processes may exhibit an increasing production rate as the lot size increases, which results in increasing efficiency in per-unit production. The degree to which this learning is carried forward into the next lot varies by process. Sometimes the learning effect experiences a 100% carryover into the next lot, but other times some learning is forgotten and there is less than a 100% carryover. We consider processes in which the learning effect is completely forgotten from lot to lot. In practice non-linear processes are often treated as linear. That is, the production data are collected and aggregated over time and an average production rate is calculated which leads to inaccuracies in the production schedule. Here we use a discretised linear model to approximate the non-linear process. Production occurs in discrete time periods within which the amount produced is known. This enables a production schedule to be determined that minimises production and holding costs. A dynamic programming model that starts with the latest demand and progresses towards the earliest demand is used to solve the single-product single-machine problem. The model is tested using the production function from the PR#2 grinding process at CTS Reeves, a manufacturing firm in Carlisle, Pa. Solution times are determined for 50, 100, 200, 500, 1500, and 3000 periods.     

A spread-sheet model for efficient production and scheduling of a manufacturing line/cell

In this paper we develop an efficient spread-sheet production planning/scheduling model for a resource-constraint production line or a manufacturing cell that produces several products but one at a time with significant changeover time and changeover cost. There are also management and physical constraints related to the operating hours, production capacity and amount of inventory allowed. The production line/cell supplies several products to customers who pull the products according to their own operating policy (working hours) that may be different from manufacture's operating hours. We also show several real-world applications and highlight the benefits and merits of the model.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems

This article presents a fuzzy goal programming-based approach for solving a multi-objective mathematical model of cell formation problem and production planning in a dynamic virtual cellular manufacturing system. In a dynamic environment, the product mix and part demand change over a planning horizon decomposed into several time periods. Thus, the cell formation done for one period may be no longer efficient for subsequent periods and hence reconfiguration of cells is required. Due to the variation of demand and necessity of reconfiguration of cells, the virtual cellular manufacturing (VCM) concept has been proposed by researchers to utilise the benefits of cellular manufacturing without reconfiguration charges. In a VCM system, machines, parts and workers are temporarily grouped for one period during which machines and workers of a group dedicatedly serve the parts of that group. The only difference of VCM with a real CM is that machines of the same group are not necessarily brought to a physical proximity in VCM. The virtual cells are created periodically depending on changes in demand volumes and mix, as new parts accumulate during a planning horizon. The major advantage of the proposed model is the consideration of demand and part mix variation over a multi-period planning horizon with worker flexibility. The aim is to minimise holding cost, backorder cost and exceptional elements in a cubic space of machine–part–worker incidence matrix. To illustrate the applicability of the proposed model, an example has been solved and computational results are presented.     

Maintenance,shutdown and production scheduling in semiconductor robotic cells

Our approach is the first to study simultaneous scheduling of preventive maintenance, shutdowns and production for robotic cells in semiconductor manufacturing. It hereby exploits the frequent periods of overcapacity in semiconductor manufacturing to reduce wear and tear. In contrast to existing approaches, our scheduling approach is able to deal with different preventive-maintenance types. We borrow the Resource Task Network representation from the process-industry domain to represent our problem and facilitate its formulation as a mathematical model. In addition, we develop efficiency-improving constraints based on the characteristics of the preventive-maintenance activities. In numerical tests based on industry data, we show that the model generates high-quality schedules even without applying the inequalities, although the optimality gap is reduced only when including inequalities. We furthermore assess the trade-off between shutdowns and batch lead times. We compare our model’s schedule quality to (i) the simple industry practice of shutting down chambers permanently to reduce wear and tear and (ii) an approach that schedules maintenance and production sequentially. The numerical tests yield the following managerial insights. First, integrating maintenance and production scheduling has substantial advantages. Second, the practice of shutting equipment down permanently diminishes scheduling flexibility and solution quality. Third, shutdowns scheduling must also consider the impact on batch waiting times.