IC 封裝廠排程問題

Abstract

The integrated circuit packaging scheduling problem (ICPSP) is a variation of the flexible flow-shop scheduling problem, which is also a generalization of the classical flow-shop and the identical parallel-machine problems. In the integrated circuit (IC) packaging factories, the jobs are clustered by the product types, which require multiple process stage operations on a series of identical parallel machines according to the manufacturing sequences. The final operation must be completed before the due dates. The job processing time at each process stage may vary, depending on the product type of the job processed on. At each process stage, setup times between two consecutive jobs of different product types (job clusters) on the same machines are sequentially dependent. The ICPSP involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, sequentially dependent setup time, and the manufacturing sequences. The problem is, therefore, considerably more difficult to solve than the classical flow-shop scheduling and the parallel-machine scheduling problem which have been investigated extensively. In this research, we formulate the ICPSP as an IP problem to minimize the total machine workload. We demonstrate the applicability of the IP model by solving a real-world example taken from an IC packaging factory. And we also present a case study on the ICPSP, which is taken from an IC packaging factory located on the Industrial Park in Taichung, Taiwan, which covers all the manufacturing process stages where the total machine workload needs to be minimized. Our investigation considers all the constraints, thus accommodates the real situations more closely than those investigated in the existing literatures. We also presented two efficient solution procedures, called the Multiple-Stage Sequential Savings algorithm and the Multi-Stage Parallel Insertion algorithm to solve the ICPSP case, which minimizes the total machine workload. Details of the schedules for the eleven stages, and the workload for each individual machine are provided.

The integrated circuit packaging scheduling problem (ICPSP) is a variation of the flexible flow-shop scheduling problem, which is also a generalization of the classical flow-shop and the identical parallel-machine problems. In the integrated circuit (IC) packaging factories, the jobs are clustered by the product types, which require multiple process stage operations on a series of identical parallel machines according to the manufacturing sequences. The final operation must be completed before the due dates. The job processing time at each process stage may vary, depending on the product type of the job processed on. At each process stage, setup times between two consecutive jobs of different product types (job clusters) on the same machines are sequentially dependent. The ICPSP involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, sequentially dependent setup time, and the manufacturing sequences. The problem is, therefore, considerably more difficult to solve than the classical flow-shop scheduling and the parallel-machine scheduling problem which have been investigated extensively. In this research, we formulate the ICPSP as an IP problem to minimize the total machine workload. We demonstrate the applicability of the IP model by solving a real-world example taken from an IC packaging factory. And we also present a case study on the ICPSP, which is taken from an IC packaging factory located on the Industrial Park in Taichung, Taiwan, which covers all the manufacturing process stages where the total machine workload needs to be minimized. Our investigation considers all the constraints, thus accommodates the real situations more closely than those investigated in the existing literatures. We also presented two efficient solution procedures, called the Multiple-Stage Sequential Savings algorithm and the Multi-Stage Parallel Insertion algorithm to solve the ICPSP case, which minimizes the total machine workload. Details of the schedules for the eleven stages, and the workload for each individual machine are provided. 2. THE IC PACKAGING PROCESS 3 3. THE IC PACKAGING SCHEDULING PROBLEM (ICPSP) 5 4. AN INTEGER PROGRAMMING FORMULATION 9 5. SOLUTIONS FOR THE ICPSP 14 6. APPLICATIONS 18 7. A CASE STUDY 22 8. MULTI-STAGE SEQUENTIAL SAVINGS ALGORITHM 28 9. MULTI-STAGE PARALLEL INSERTION ALGORITHM 35 10. CONCLUSION 45 REFERENCES 46