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.     

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.     

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 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 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.     

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 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.     

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 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 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.     

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.     

A comparison of exhaustive and non-exhaustive group scheduling heuristics in a manufacturing cell

Previous group scheduling research has primarily focused on developing exhaustive two-stage heuristics in order to manage product flow through manufacturing cells. The objective of this paper is to present new, non-exhaustive heuristics and compare them with existing exhaustive heuristics in a job shop cell environment. Computer simulation is utilized to examine six non-exhaustive and six exhaustive heuristics under eight experimental conditions. The results indicate that although some non-exhaustive heuristics dominate the exhaustive heuristics on the average tardiness measure, the performance of exhaustive heuristics are generally superior to that of non-exhaustive heuristics. Furthermore, the performance of the exhaustive heuristics is more robust to the experimental factors.     

A study of scheduling rules of flexible manufacturing systems: A simulation approach

This study examines the effects of scheduling rules on the performance of flexible manufacturing systems (FMSs). Several machine and AGV scheduling rules are tested against the mean flowtime criterion. In general, scheduling rules are widely used in practice ranging from direct applications as a stand-alone scheduling scheme to indirect application as a part of complicated scheduling systems. In this paper, we compare the rules under various experimental conditions by using an FMS simulation model. Our objective is to measure sensitivity of the rules to changes in processing time distributions, various levels of breakdown rates, and types of AGV priority schemes. A comprehensive bibliography is also presented in the paper.     

A multi-objective scatter search for the ladle scheduling problem

We consider the ladle scheduling problem, which can be regarded as a vehicle routing problem with semi-soft time windows and adjustment times. The problem concerns allocating ladles to serve molten steel based on a given steelmaking scheduling plan, and determining the modification operations for the empty ladles after the service process. In addition, combining the controllable processing time of molten steel, the other aspect of the problem is to determine the service start times taking into consideration the technological constraints imposed in practice. We present a non-linear mathematical programming model with the conflicting objectives of minimising the occupation ratio of the ladles and maximising the degree of satisfaction with meeting the soft windows. To solve the multi-objective model, we develop a new scatter search (SS) approach by re-designing the common components of SS and incorporating a diversification generator, a combination method and a diversification criterion to conduct a wide exploration of the search space. We analyse and compare the performance of the proposed approach with a multi-objective genetic algorithm and with manual scheduling adopted in practical production using three real-life instances from a well-known iron–steel production plant in China. The computational results demonstrate the effectiveness of the proposed SS approach for solving the ladle scheduling problem.     

A two-machine permutation flow shop scheduling problem with buffers

Problems with blocking (limited intermediate storage space) are used frequently for modelling and scheduling just-in-time and flexible manufacturing systems. In this paper, an approximation algorithm is presented for the problem of finding the minimum makespan in a two-machine permutation flow-shop scheduling problem with the mediating buffer of finite capacity. The algorithm is based on the tabu search approach supported by the reduced neighborhood, search accelerator and technique of back jumps on the search trajectory. Due to some special properties, the proposed algorithm provides makespans very close to optimal in a short time. It has been shown that this algorithm outperforms all known approximation algorithms for the problem stated.     

A flowshop scheduling problem with two operations per job

This paper considers a special case of the flowshop scheduling problem where each job requires only two operations on specified machines and shows that this problem is NP-hard in the strong sense even if the first operation of all jobs is processed on the same machine and the number of machines performing the second operation equals two. For the case when the first operation of all jobs is performed on the same machine, it is sufficient to consider only permutation schedules for minimizing any regular measure of performance. Five polynomially bounded heuristic algorithms are described for minimizing makespan for this case and their performance in finding a minimum makespan schedule is theoretically and empirically evaluated.