Search

In this paper, we consider an inventory–routing problem (IRP) in a large petroleum and petrochemical enterprise group. Compared to many other IRPs, the problem in this paper includes some special aspects due to the operational constraints, such as hours-of-service regulations of the company and the industry. Also, in some cases, it is more important to avoid stock out for any station, rather than purely focusing on transportation cost minimization. The objective is to minimize the maximum of the route travel time, which is not addressed in the literature so far. We present a tabu search algorithm to tackle the problem, which builds in an efficient and effective procedure to improve the search quality in each iteration. Moreover, lower bounds of reasonable sized problems, which are intractable in the formulated mathematical model by existing optimization software, are obtained via Lagrangian relaxation technique. Computational results indicate that the lower bounds are tight and the tabu search is capable of providing near optimal, close-to-lower-bound solutions in a computational time effective manner.

In this research, we study a supply chain which consists of a firm and a set of customer groups, where the demand (order quantity) from each customer group depends on the quoted delivery time. The prices of the product are determined and different to each customer group. The firm's objective is to maximize the profit by quoting different delivery times for all customer groups. A mathematical model is developed, which is proved to be NP hard. Both a mixed integer programming (MIP) formulation and the branch-and-bound algorithm are proposed to study the moderate size of the problem. Also, a heuristic algorithm is developed which is able to obtain the optimal solution quickly in most of cases when customer size is less than 20.

We consider a two-stage manufacturing system composed of a batch processor and its upstream processor. Jobs exit the upstream processor and join a queue in front of the batch processor, where they wait to be processed. The batch processor has a finite capacity Q, and its processing time is independent of the number of jobs loaded into the batch processor. In certain manufacturing systems (including semiconductor wafer fabrication), a processing time window exists from the time instance the job exits the upstream processor till the time instance it enters the batch processor. If a job is not processed before reaching the end of its processing time window, job rework or validation is required. We model this drawback by assigning a reward R for each successfully processed job by the upstream processor, and a penalty C for each job that reaches the end of its processing time window without being processed by the batch processor. We initially assume an infinite job source in front of the serial processor and also assume that the batch processor is operated under a threshold policy. We provide a method for controlling the production of the serial processor, considering the processing time window between the upstream processor and the downstream batch processor. We then show how the serial processor control policy can be modified when the serial processor also experiences intermittent job arrival.

We examine the problem of minimizing the mean cycle time of a batch processor with incompatible job families and future job arrivals. Batch processors frequently found in wafer fabrication include oxidation and diffusion ovens. When the problem is deterministic with a fixed number of job arrivals, the problem is NP-hard; an optimal dynamic program formulation is developed and empirically tested on small problem instances. For larger problem instances with possibly infinite job arrivals, an online heuristic based on model predictive control (MPC) is proposed. The proposed heuristic has two parameters: the number of job families considered f, and the number of future job arrivals L. Statistical analysis of simulation results shows that the MPC-based heuristic has significantly lower mean cycle time than a benchmark look-ahead method under the assumption that the arrival time is deterministic and job families of consecutive job arrivals are uncorrelated. These observations also hold true when the predicted arrival times can be erroneous, indicating that the suggested MPC-based heuristic is as robust as the benchmark with respect to errors in forecasted arrival times. When the job families of future job arrivals are positively correlated, the mean cycle time of jobs passing through the batch processor is significantly reduced, regardless of control policy. We infer that the introduction of correlation generates less improvement for policies that foresee events longer into the future. For this reason, when the correlation is high, the MPC-based heuristic, which considers events that occur farther into the future, may have worse performance than the benchmark. The results suggest two ways to improve the performance of the batch processor. First, we can use a heuristic that has better mean performance, which may entail much larger computational costs. Another option is to continue using a simple look-ahead policy at the batch processor, and focus attention on controlling the upstream processors, such that the batch processor arrival process exhibits correlated job families between consecutive arrivals. This introduction of correlation causes a significant reduction of cycle time regardless of system parameter and batch processor control policy.

The problem of routing and scheduling military convoys adhering to certain constraints is known as the convoy movement problem. This work addresses a bi-criteria model for the peacetime version of the convoy movement problem with minimizing total travel time and travel span as objectives. Two approaches, one based on goal programming and the other based on simulated annealing, are proposed. Encouraging results have been obtained.

This paper presents a new job release methodology: WIPLOAD Control (WIPLCtrl), which is a workload limited release methodology for the overall shop floor. The behaviour of WIPLCtrl is analyzed using the Markov process model of a transfer line system to observe the potential advantage of WIPLCtrl relative to the conventional measure of system workload using the WIP level. A simulation experiment is then conducted considering a simplified semiconductor wafer fabrication system. The performance of WIPLCtrl is compared with that of an open-loop release methodology and three other closed-loop workload limited release methodologies. A case study is also carried out by simulating a real-life wafer fabrication, considering the complexities and the distinguishing features of semiconductor manufacturing. The experimental results indicate that WIPLCtrl is an efficient job release methodology, capable of reducing both the mean and the standard deviation of the cycle time for a given throughput level. The performance ...

Nowadays, it is popular to outsource transportation and distribution of finished products to third-party logistics (3PL) providers in many industries. In order to shorten the response time from order receipt to delivery, and also to improve on-time delivery accuracy, the decision of manufacturing scheduling and transportation scheduling should consider the constraints between manufacturing and transportation. In this paper, we study a coordinated scheduling problem of parallel machine assembly manufacturing and multi-destination transportation in the make-to-order (MTO) consumer electronics supply chain (CESC). By considering the constraints between parallel machine assembly and 3PL transportation, the overall problem is decomposed into a parallel machine scheduling sub-problem and a 3PL transportation sub-problem. The 3PL transportation problem is proved to be NP-complete. Heuristic algorithms are proposed to solve the parallel machine assembly scheduling problem.

This paper validates a proposed job release methodology and experimentally investigates the impact of production control methodologies and system factors on wafer fab performance in terms of average cycle time, standard deviation of cycle time, average lateness, WIP inventory and fab output by simulating a wafer fab of Chartered Semiconductor Manufacturing Ltd (Chartered) and statistically analyzing the experimental results using t-test and ANOVA. A full factorial design of experiment is conducted to evaluate the performance of three job release methodologies, three dispatching rules and three greedy levels of batching policy under different system environmental settings differentiated by fab output level and machine unreliability level. Based on the experimental results, the proposed job release methodology WIPLOAD control (WIPLCtrl) appears to be very efficient to be able to potentially improve all the considered performance measures simultaneously. The advantage of WIPLCtrl is robust to the change of system environmental conditions. In contrast, the improvement brought by a dispatching rule on a certain performance measure might cost the deterioration of other performances. Considering the relative impact on the fab performance, job release control appears to be the most important production control factor in comparison with dispatching and batching policy, especially when the system is operating on a high output level and/or with a high system variability level caused by machine unreliability.

In this paper, we study the minimization of variance of cycle times in a dynamic single machine system where jobs arrive continuously over time. Numerous production systems give rise to single machine models, and a multiple-machine environment where the performance of a bottleneck machine determines the performance of the entire system reduces to a single machine problem [16]. Minimizing cycle time variance helps in safe predictions of the completion of job production and thus in providing the same quality of service to the customers. This allows an improved ability to meet the due dates reliably, and thus the greater coordination with further downstream operations on the jobs, as highly preferred in semiconductor manufacturing. Scheduling the bottleneck process to minimize the time of presence of the jobs in process minimizes the deterioration of cycle time-related performance measures. Low values of cycle time-related measures are also preferred for low risk of wafer contamination associated with it during processing. New scheduling rules are developed to minimize both the cycle time variance and the maximum cycle time for single machine system, wherein the machine/process is always utilized to the maximum extent and in the extreme case is heavily loaded with jobs for processing. The performance of the proposed rules is compared with the rules available in the literature and the results are presented for the objectives of minimizing cycle time variance and maximum cycle time at higher levels of machine utilization.

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.

With the advent of the Just-In-Time (JIT) manufacturing philosophy, scheduling problems with delivery performance have received significant attention in recent years. The JIT concept requires not only a penalty for lateness but also for earliness and therefore both early and tardy deliveries are highly discouraged. In this paper, the dynamic scheduling of a single batch processing machine has been addressed for controlling the delivery performance between earliness and tardiness measures. A Look Ahead Batching (LAB) strategy has been proposed. In LAB, the scheduling decisions are made considering the arrival epochs and due dates of the incoming lots, which are easily predictable in a computer-integrated manufacturing environment, especially in the semiconductor industry. LAB strategy is used to control the delivery performance, which involves a trade-off between the conflicting objectives of minimizing earliness- and tardiness-related measures simultaneously. The potential of LAB strategy in controlling d...

This paper considers how to schedule appointments for outpatients, for a clinic that is subject to appointment lead-time targets for both new and returning patients. We develop heuristic rules, which are the exact and relaxed appointment scheduling rules, to schedule each new patient appointment (only) in light of uncertainty about future arrivals. The scheduling rules entail two decisions. First, the rules need to determine whether or not a patient's request can be accepted; then, if the request is not rejected, the rules prescribe how to assign the patient to an available slot. The intent of the scheduling rules is to maximize the utilization of the planned resource (i.e., the physician staff), or equivalently to maximize the number of patients that are admitted, while maintaining the service targets on the median, the 95th percentile, and the maximum appointment lead-times. We test the proposed scheduling rules with numerical experiments using real data from the chosen clinic of Tan Tock Seng hospital in Singapore. The results show the efficiency and the efficacy of the scheduling rules, in terms of the service-target satisfaction and the resource utilization. From the sensitivity analysis, we find that the performance of the proposed scheduling rules is fairly robust to the specification of the established lead-time targets.

In this paper, the problem of minimizing total absolute differences of completion times (TADC) of jobs and mean flowtime is studied. The objective of minimizing TADC ensures the completion times of jobs are close to one another, while the objective of minimizing mean flowtime minimizes the average time spent by the jobs in the system. Early completion of jobs is not desirable in delivery situations when jobs have to be dispatched together for a customized delivery or assembly and, particularly, when the finished jobs incur costs for preserving/holding them till other matching job orders complete. In this work, lower bounds on TADC and mean flowtime subject to minimum TADC for the static jobshop problem are reported. A simulated annealing algorithm using the concept of backward scheduling is proposed for minimizing mean flowtime subject to optimal TADC, and the proposed algorithm is evaluated using 82 jobshop scheduling problems taken from literature, of size varying from 6-jobs 6-machines to 50-jobs 20-machines. Finally, we combine a statistical optimum prediction technique with the proposed simulated annealing algorithm, and evaluate the statistical bounds established for the objective of minimizing mean flowtime subject to minimum TADC on the benchmark problems.

This paper presents look-ahead batch scheduling for the real-time control of due-date objectives, such as average tardiness, maximum tardiness, and number of tardy jobs in batch processes. These due-date objectives play an important role in several production industries such as semiconductor manufacturing, aircraft industry, metalworking industry, etc. In look-ahead batching, the scheduling decisions are based on the arrival epochs and due-dates of incoming lots at each work station which are easily predictable in a computer integrated manufacturing environment. The steady state performance of the developed control strategy is compared to the steady state performance of the theoretically optimal control strategy (i.e. a Minimum Batch Size strategy). The experimental results indicate that the developed look-ahead batch scheduling strategy improves the performance of due-date objectives under wide conditions of arrival pattern, due-date distribution and traffic intensity.

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.

A discrete event simulation based "online near-real-time" dynamic multiobjective scheduling system has been conceptualized, designed, and developed to achieve Pareto optimal solutions in a complex manufacturing environment of semiconductor back-end. Our approach includes the use of linear weighted aggregation optimization approach for multiple objectives and auto simulation model generation for online simulation. Developed concepts are implemented at a semiconductor back-end site and are in use. The impact of the system includes a better customer delivery achievement, consistent cycle time with narrower distribution, improved machine utilization, reduction in the time that planners and manufacturing personnel spend on scheduling, and more predictable and repeatable manufacturing performance. In addition, it enables managers and senior planners to carry out "what now" analysis to make effective current decisions and "what if" analysis to plan for the future.

This paper presents a preliminary analysis of the typical scheduling environment in semiconductor manufacturing involving multiple job families, and where more than one objective such as cycle time, machine utilization and the due-date accuracy needs to be simultaneously considered. In this study, the NP-hard 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, to minimize average tardiness, and to maximize machine utilization. A Pareto optimal solution, which is not inferior to any other feasible solutions 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, a Pareto optimal lot is selected using the compromise programming technique for multiobjective optimization at each decision instant in simulated time. With the help of a broad experimental design, this developed solution is then compared with common heuristic-dispatching rules such as SPT and EDD, which show better results for all the objectives over a wide range of problems. The developed scheduling method 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.

The paper studies the problem of synchronizing air transportation and assembly manufacturing to achieve accurate delivery with minimized cost in a consumer electronics supply chain. The motivation for this study came from a major computer manufacturer in a consumer electronics industry that faces challenges in the final stages of delivery of a supply chain. The synchronization problem is decomposed and formulated as two sub-problems, i.e. a multi-destination air transportation allocation problem and an assembly-scheduling problem. The first sub-problem is formulated and solved as an integer linear programming problem. For the assembly-scheduling problem, two solution methodologies using the concepts of forward and backward scheduling are presented. Computational results indicate that the proposed methodologies can achieve considerable cost reduction compared with the existing methodology applied in industry.

This paper presents a brief review on job shop scheduling techniques in semiconductor manufacturing. The manufacturing environment in a semiconductor industry is considered a highly complex job shop, involving multiple types of work centers, large and changing varieties of products, sequence-dependent setup times, reentrant process flow, etc., in a dynamic scheduling environment. Due to the stubborn nature of the deterministic job shop scheduling problem itself, many of the solutions proposed are of hybrid construction cutting across the traditional disciplines. The problem has been investigated from a variety of perspectives resulting in several analytical techniques combining generic as well as problem-specific strategies. In this paper, we seek to provide a brief overview of the problem, the techniques used and the researchers involved in solving this problem.

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.