This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.

This research focuses on a scheduling problem in the semiconductor probing facility. Probing facility is composed of identical parallel machines and the parallel machines form three workstations for the tests with different recipes. Each machine can be set to three different tests and sequence-dependent setup times are required between operations due to temperature and probe card loading/unloading. Precedence relationship exists between three tests of each wafer lot. The scheduling problem for the probing facility is a parallel machine scheduling problem with precedence relationship and sequence dependent setup time. We develop heuristic algorithm to minimize makespan for the scheduling problem and numerical experiments are conducted to evaluate the performance.

This study focuses on the formation of input release lots in a semiconductor wafer fabrication facility. After the order-lot pegging process assigns lots in the fab to orders and calculates the required quantity of wafers for each product type to meet customers’ orders, the decisions on the formation of input release lots should be made to minimize the production costs of the release lots. Since the number of lots being processed in the wafer fab directly is related to the productivity of the wafer fab, the input lot formation is crucial process to reduce the production costs as well as to improve the efficiency of the wafer fab. Here, the input lot formation occurs before every shift begins in the semiconductor wafer fab. When input quantities (of wafers) for product types are given from results of the order-lot pegging process, lots to be released into the wafer fab should be formed satisfying the lot size requirements. Here, the production cost of a homogeneous lot of the same type of product is less than that of a heterogeneous lot that will be split into the number of lots according to their product types after passing the branch point during the wafer fabrication process. Also, more production cost occurs if a lot becomes more heterogeneous. We developed a multi-dimensional dynamic programming algorithm for the input lot formation problem and showed how to apply the algorithm to solve the problem optimally with an example problem instance. It is necessary to reduce the number of states at each stage in the DP algorithm for practical use. Also, we can apply the proposed DP algorithm together with lot release rules such as CONWIP and UNIFORM.

We consider a wafer lot transfer/release planning problem from semiconductor wafer fabrication facilities to probing facilities with the objective of minimizing the deviation of workload and total tardiness of customers’ orders. Due to the complexity of the considered problem, we propose a two-level hierarchical production planning method for the lot transfer problem between two parallel facilities to obtain an executable production plan and schedule. In the higher level, the solution for the reduced mathematical model with Lagrangian relaxation method can be regarded as a coarse good lot transfer/release plan with daily time bucket, and discrete-event simulation is performed to obtain detailed lot processing schedules at the machines with a priority- rule-based scheduling method and the lot transfer/release plan is evaluated in the lower level. To evaluate the performance of the suggested planning method, we provide computational tests on the problems obtained from a set of real data and additional test scenarios in which the several levels of variations are added in the customers’ demands. Results of computational tests showed that the proposed lot transfer/planning architecture generates executable plans within acceptable computational time in the real factories and the total tardiness of orders can be reduced more effectively by using more sophisticated lot transfer methods, such as considering the due date and ready times of lots associated the same order with the mathematical formulation. The proposed method may be implemented for the problem of job assignment in back-end process such as the assignment of chips to be tested from assembly facilities to final test facilities. Also, the proposed method can be improved by considering the sequence dependent setup in the probing facilities.

We focus on the fire scheduling problem (FSP), the problem of determining the sequence of targets to be fired at, for the objective of minimizing makespan to achieve tactical goals. In this paper, we assume that there are m available weapons to fire at n targets (> m) and the weapons are already allocated to targets. One weapon or multiple weapons can fire at one target and these fire operations should start simultaneously while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm implementing them. Also, In addition, heuristic algorithms that can be used for obtaining an initial upper bound in the B&B algorithm and for obtaining good solutions in a short time were developed. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time. The proposed lower bound, the dominance properties, and the heuristics for upper bound are tested in B&B respectively, and the result showed that lower bound is effective to fathoming nodes and the dominance properties and heuristics also worked well. Also, it is showed that the CPU time required by this algorithm increases rapidly as the problem size increases. Therefore, the suggested B&B algorithm would be limited to solve large size problems. However, the employed heuristic algorithms can be effectively used in the B&B algorithm and can give good solutions for large problems within a few seconds.

This paper addresses order-lot pegging issues in the supply chain of a semiconductor business. In such a semiconductor business (memory or system LSI) order-lot pegging issues are critical to achieving the goal of ATP (Available to Promise) and on-time production and delivery. However existing pegging system and researches do not consider capacity limit on bottleneck steps. This paper presents an order-lot pegging algorithm for assigning a lot to an order considering quality constraints of each lot and capacity of bottleneck steps along the entire FAB. As a result, a quick and accurate response can be provided to customer order enquiries and pegged lot lists for each promised orders can be shown transparently and short or late orders can be detected before fixing the order.