Full metadata record
DC FieldValueLanguage
dc.contributor.authorMing-Hsien Yangen_US
dc.contributor.authorWen-Lea Pearnen_US
dc.contributor.authorShu-Hsing Chungen_US
dc.description.abstractThe wafer probing scheduling problem (WPSP) is a practical generalization of the classical parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which are processed on groups of identical parallel machines and must be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this research, we formulate the WPSP as an integer programming problem to minimize the total machine workload. To demonstrate the applicability of the integer programming model, we solved a real-world WPSP using the powerful CPLEX with effective implementation strategies, so that solutions may be obtained within reasonable amount of time. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the concept of proposed transformation, we present nine efficient algorithms to solve the WPSP near-optimally, where these algorithms are developed by modifying the savings and insertion algorithms for VRPTW. The performances of these nine algorithms are also tested by problems in literature and by real world WPSP case. 中文摘要 II 誌 謝 III CONTENTS IV LIST OF TABLES V LIST OF FIGURES VII 1. INTRODUCTION 1 2. PROBLEM DESCRIPTION 5 2.1. THE WAFER PROBING PROCESS 5 2.2. THE WAFER PROBING SCHEDULING PROBLEM (WPSP) 6 3. AN INTEGER PROGRAMMING MODEL FOR THE WPSP 9 3.1. AN INTEGER PROGRAMMING FORMULATION 9 3.2. SOLUTIONS FOR THE WPSP EXAMPLE 13 3.3. SOLUTIONS FOR THE WPSP CASE 16 4. A NETWORK TRANSFORMATION 21 4.1. THE DEFINITIONS OF NODES AND ARCS 21 4.2. THE DEFINITIONS OF TIME WINDOWS AND NODE DEMAND 23 4.3. THE EQUIVALENCE OF VRPTW TOURS AND WPSP SCHEDULES 23 4.4. AN EXAMPLE OF THE NETWORK TRANSFORMATION 26 4.5. A REAL-WORLD APPLICATION 29 5. ALGORITHMS FOR SOLVING THE WPSP 35 5.1. THE DESIGN OF ALGORITHMS 36 5.1.1. Matching based savings algorithm 36 5.1.2. Matching-based with compound-savings algorithm 38 5.1.3. Sequential savings algorithm 39 5.1.4. Parallel savings algorithm 40 5.1.5. Generalized savings algorithm 41 5.1.6. Potvin and rousseau’s parallel insertion algorithm 43 5.1.7. Nearest insertion algorithm 45 5.1.8. Cheapest insertion algorithm 45 5.1.9. Farthest insertion algorithm 46 5.2. COMPUTATIONAL RESULTS 47 5.3. PERFORMANCE COMPARISON 48 6. CONCLUSIONS 51 REFERENCES 52 APPENDIX A 55en_US
dc.subjectIdentical parallel-machine schedulingen_US
dc.subjectWafer probingen_US
dc.subjectInteger programmingen_US
dc.subjectVehicle routing with time windowsen_US
dc.titleThe Wafer Probing Scheduling Problem (WPSP): on Identical Parallel-Machine Modeling, Algorithms, and Applicationsen_US
Appears in Collections:Thesis