Ordering scheduling problem in manufacturing systems

The problem of scheduling customer orders in the management of a large multi-product warehouse is addressed under realistic assumptions including rapidly changing data, uncertainties and unforeseen events. Simple flexible solution strategies are sought, in the sense that the scheduling problem should not be solved again from the beginning every time new information becomes available. Among the solution strategies, one is based on a few statistical assumptions about the random variables involved in the process: it exploits a stochastic version of the well-known duality principle for nonlinear programming and yields a number of interesting features.     

Biogeography-based optimisation for flexible manufacturing system scheduling problem

Biogeography-based optimisation (BBO) algorithm is a new evolutionary optimisation algorithm based on geographic distribution of biological organisms. With probabilistic operators, this algorithm is able to share more information from good solutions to poor ones. BBO prevents the good solutions to be demolished during the evolution. This feature leads to find the better solutions in a short time rather than other metaheuristics. This paper provides a mathematical model which integrates machine loading, part routing, sequencing and scheduling decision in flexible manufacturing systems (FMS). Moreover, it tackles the scheduling problem when various constraints are imposed on the system. Since this problem is considered to be NP-hard, BBO algorithm is developed to find the optimum /near optimum solution based on various constraints. In the proposed algorithm, different types of mutation operators are employed to enhance the diversity among the population. The proposed BBO has been applied to the instances with different size and degrees of complexity of problem adopted from the FMS literature. The experimental results demonstrate the effectiveness of the proposed algorithm to find optimum /near optimum solutions within reasonable time. Therefore, BBO algorithm can be used as a useful solution for optimisation in various industrial applications within a reasonable computation time.     

A note on the problem of scheduling a flexible manufacturing system for Just-in-time customers

In supplying just-in-time customers, one common industry practice is for the vendor to set up a warehouse near the point of demand. We assume that the plant is a flexible manufacturing system (FMS) where the changeover times between parts of the same family axe. negligible, but not between parts of different families. Thus the FMS must be configured to produce one family of parts at a time. For each part type, we assume that the vendor makes deliveries to the warehouse at fixed intervals. We examined two related issues: the run length for each part family and the number of deliveries to the warehouse in each cycle. We first showed that it is not necessary for the vendor to produce for each delivery, nor is it desirable to complete the entire production lot before delivery. We then investigated the FMS loading problem for two or more part-families. We developed the expressions for the optimal run length and delivery frequency, (1) when loading the part types sequentially and (2) when loading the part types simultaneously. The resulting models can be shown to be consistent with the classical EOQ model.     

An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production

Energy-efficient scheduling is highly necessary for energy-intensive industries, such as glass, mould or chemical production. Inspired by a real-world glass-ceramics production process, this paper investigates a bi-criteria energy-efficient two-stage hybrid flow shop scheduling problem, in which parallel machines with eligibility are at stage 1 and a batch machine is at stage 2. The performance measures considered are makespan and total energy consumption. Time-of-use (TOU) electricity prices and different states of machines (working, idle and turnoff) are integrated. To tackle this problem, a mixed integer programming (MIP) is formulated, based on which an augmented ε-constraint (AUGMECON) method is adopted to obtain the exact Pareto front. A problem-tailored constructive heuristic method with local search strategy, a bi-objective tabu search algorithm and a bi-objective ant colony optimisation algorithm are developed to deal with medium- and large-scale problems. Extensive computational experiments are conducted, and a real-world case is solved. The results show effectiveness of the proposed methods, in particular the bi-objective tabu search.     

A decentralised multi-objective scheduling methodology for semiconductor manufacturing

This paper presents a decentralised multi-objective scheduling methodology for semiconductor manufacturing. In this methodology, a new classification method is designed based on utilisations and entropies in order to decentralise global objectives into local ones of work stations. Then, a decentralised multi-objective scheduling policy is proposed to control virtual production lines (VPLs) and machine workload. Results of numerical experiments show that the proposed methodology outperforms common rule-based scheduling policies and a compound scheduling strategy.     

A scheduling approach for a flexible manufacturing system

This paper discusses the scheduling problem of a particular flexible manufacturing system (FMS). The two main components of the FMS are a CNC turret lathe and a CNC machining centre. In the system a wide range of different jobs has to be processed. Each job consists of one or more processing operations on one or both machines. Important characteristics of the scheduling problem are sequence-dependent change-over times (on the turret lathe) and transfer times (on both machines and between the machines). The change-over times are caused by the need to exchange tools in the turret when a new part is going to be processed. The transfer times reflect the time needed to perform manual transportation and clamping activities between two subsequent processing (machining) operations of a part. In this paper a branch and bound algorithm is described based on an active schedule strategy. Solutions are compared to results obtained by a simple dispatching rule     

A learning-based methodology for dynamic scheduling in distributed manufacturing systems

To enhance productivity in a distributed manufacturing system under hierarchical control, we develop a framework of dynamic scheduling scheme that explores routeing flexibility and handles uncertainties. We propose a learning-based methodology to extract scheduling knowledge for dispatching parts to machines. The proposed methodology includes three modules: discrete-event simulation, instance generation, and incremental induction. First, a sophisticated simulation module is developed to implement a dynamic scheduling scheme, to generate training examples, and to evaluate the methodology. Second, the search for training examples (good schedules) is successfully fulfilled by the genetic algorithm. Finally, we propose a tolerance-based learning algorithm that does not only acquire general scheduling rules from the training examples, but also adapts to any newly observed examples and thus facilitates knowledge modification. The experimental results show that the dynamic scheduling scheme significantly outperforms the static scheduling scheme with a single dispatching rule in a distributed manufacturing system.     

Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems

Multi-factory production networks have increased in recent years. With the factories located in different geographic areas, companies can benefit from various advantages, such as closeness to their customers, and can respond faster to market changes. Products (jobs) in the network can usually be produced in more than one factory. However, each factory has its operations efficiency, capacity, and utilization level. Allocation of jobs inappropriately in a factory will produce high cost, long lead time, overloading or idling resources, etc. This makes distributed scheduling more complicated than classical production scheduling problems because it has to determine how to allocate the jobs into suitable factories, and simultaneously determine the production scheduling in each factory as well. The problem is even more complicated when alternative production routing is allowed in the factories. This paper proposed a genetic algorithm with dominant genes to deal with distributed scheduling problems, especially in a flexible manufacturing system (FMS) environment. The idea of dominant genes is to identify and record the critical genes in the chromosome and to enhance the performance of genetic search. To testify and benchmark the optimization reliability, the proposed algorithm has been compared with other approaches on several distributed scheduling problems. These comparisons demonstrate the importance of distributed scheduling and indicate the optimization reliability of the proposed algorithm.     

Multi-objective master production scheduling in make-to-order manufacturing

In this paper a multi-objective, long-term production scheduling in make-to-order manufacturing is considered and a lexicographic approach with a hierarchy of integer programming formulations is proposed. The problem objective is to allocate customer orders with various due dates among planning periods with limited capacities to minimize the number of tardy orders as a primary optimality criterion. Then, the maximum level of the input and output inventory is minimized as a secondary criterion, and finally the aggregate production is leveled over the planning horizon as an auxiliary criterion. A close relation between minimizing the maximal inventory and the maximum earliness of customer orders is shown and used to simplify the inventory leveling problem. Numerical examples, modeled after a real-world make-to-order flexible flowshop in a high-tech industry, are provided and some computational results are reported. The paper indicates that the maximum earliness of customer orders is an important managerial decision variable, and its minimum value can be applied to control the inventory of purchased materials and finished products to maximize the customer service level and minimize production costs.     

A method for scheduling in parallel manufacturing systems with flexible resources

We address the Parallel-Machine Flexible-Resource Scheduling (PMFRS) problem of simultaneously allocating flexible resources, and sequencing jobs, in cellular manufacturing systems where the cells are configured in parallel. We present a new solution methodology for the PMFRS problem called the Nested Partitions (NP) method. This method combines global sampling of the feasible region and local search heuristics. To efficiently apply the NP method we reformulate the PMFRS problem, develop a new sampling algorithm that can be used to obtain good feasible schedules, and suggest a new improvement heuristic. Numerical examples are also presented to illustrate the new method.     

A batching and scheduling algorithm for the diffusion area in semiconductor manufacturing

This paper proposes an efficient heuristic algorithm for solving a complex batching and scheduling problem in a diffusion area of a semiconductor plant. Diffusion is frequently the bottleneck in the plant and also one of the most complex areas in terms of number of machines, constraints to satisfy and the large number of lots to manage. The purpose of this study is to investigate an approach to group lots in batches and to schedule these batches on machines. The problem is modelled and solved using a disjunctive graph representation. A constructive algorithm is proposed and improvement procedures based on iterative sampling and Simulated Annealing are developed. Computational experiments, carried out on actual industrial problem instances, show the ability of the iterative sampling algorithms to significantly improve the initial solution, and that Simulated Annealing enhances the results. Furthermore, our algorithm compares favourably to an algorithm reported in the literature for a simplified version of our problem. The constructive algorithm has been embedded in software and is currently being used in a semiconductor plant.     

A parallel-machine scheduling problem with two competing agents

Scheduling with two competing agents has become popular in recent years. Most of the research has focused on single-machine problems. This article considers a parallel-machine problem, the objective of which is to minimize the total completion time of jobs from the first agent given that the maximum tardiness of jobs from the second agent cannot exceed an upper bound. The NP-hardness of this problem is also examined. A genetic algorithm equipped with local search is proposed to search for the near-optimal solution. Computational experiments are conducted to evaluate the proposed genetic algorithm.     

A survey on the resource-constrained project scheduling problem

In this paper, research on the resource-constrained project scheduling problem is classified according to specified objectives and constraints. Each classified area is extensively surveyed, and special emphasis is given to trends in recent research. Specific papers involving nonrenewable resource constraints and time/cost-based objectives are discussed in detail because they present models that are close representations of real-world problems. The difficulty of solving such complex models by optimization techniques is noted. For the purposes of this survey, a set of 78 optimally solved test problems from the literature and a second set of 110 benchmark problems have been subjected to analysis with some well-known dispatching rules and a scheduling algorithm that consists of a decision-making process utilizing the problem constraints as a base of selection. The computational results are reported and discussed in the text. Constructive scheduling algorithms that are directly based on the problem constraints and whose performances are independent of problem characteristics are identified as a promising area for future research.     

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

The problem of scheduling in flowshop and flowline-based manufacturing cell is considered with the bicriteria of minimizing makespan and total flowtime of jobs, The formulation of the scheduling problems for both the flowshop and the flowline-based manufacturing cell is first discussed. We then present the development of the proposed heuristic for flowshop scheduling. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to bicriteria, The proposed heuristic algorithm as well as the existing heuristic are evaluated in a large number of randomly generated large-sized flowshop problems. We also investigate the effectiveness of these heuristics with respect to the objective of minimizing total machine idletime. We then modify the proposed heuristic for scheduling in a cell, and evaluate its performance.     

A bottleneck-based beam search for job scheduling in a flexible manufacturing system

In this paper, we study job-scheduling methods for flexible manufacturing systems (FMSs). Routeing flexibility is a feature that distinguishes FMS scheduling from a classic general jobshop problem. We formalize the problem as a flexible jobshop problem and introduce a flexibility index to measure the extent of routeing flexibility. Based on a procedure to identify a potential bottleneck machine, we develop a beam search method for approximately solving the problem. The proposed method yields a significantly shorter makespan than that of the commonly used shortest processing-time dispatching rule, and it properly exploits the added flexibility in routeing. The computational effort required also is small enough to enable practical implementation.     

On-line scheduling in a multi-cell flexible manufacturing system

This paper deals with on-line scheduling in a multi-cell flexible manufacturing system, operating in a produce-to-order environment. A two level distributed production control system (DPCS) is developed and tested through a simulation study. The DPCS allows autonomous and simultaneous operation of each cell-controller, utilizing only local and short term information as well as simple heuristic rules. Simulation experiments show that the proposed DPCS achieves good results in throughput, tardiness of orders and WIP inventory level and that it is robust to machine and handling device failures.     

Distributed computing approaches toward manufacturing scheduling problems

This paper investigates the solution of manufacturing scheduling problems using different distributed computer schemes. The distributed computer schemes vary with respect to task partitioning, task allocation and the number of processors used. The best combinations of these variations are presented with respect to problem scenario and size. The distributed computing models, are analyzed with respect to computational advantages gained vs. traditional computing models. The models are implemented over a distributed computer network, designed for heterogeneous application, and are transportable to other operating systems and networks of computers. The advantages of these models are discussed and several useful extensions are presented.