| dc.description.abstract | The manufacturing industries play a significant role in contributing to the economy of a country. Among various manufacturing industries, the semiconductor manufacturing (SM) industries is one of the fastest growing industries in the world having worldwide sales of $31 billion in the month of December 2016. Semiconductors are required by large number of industries, including Telecommunications, Medical Electronics, Automobile, Defence and Aerospace, Consumer Electronics, etc.,. Today, without semiconductors, the technology that we count on every day would not be possible. Because of these, the demand for SM industry is increased rapidly. In addition, most of the semiconductor based products‘ life is very short. Due to these, SM industry is highly competitive industry. Thus, to utilize the resources effectively, to handle the huge demand, and to deliver the product on-time, efficient scheduling is important in SM industry.
SM process can be broadly classified into Wafer Fabrication (called as wafer fab), Wafer Probing, Assembly, and Final Testing. Scheduling is more important in wafer fab due to complex operations involving with multiple types of machines and re-entrant, expensive machines, and time-consuming process involved. Thus, this study concerns about scheduling in wafer fab, particularly diffusion operation. The diffusion operation, carried out on batch processing machine, heavily impacts the production rate of wafer fab and in turn the SM industry. This is due to the fact that, diffusion operation requires relatively longest processing time among all the operations in the wafer fab. Due to these, diffusion operation is the bottleneck operations in the wafer fab.
Based on the detailed literature review, this study addresses a new research problem on dynamic scheduling (DS) of diffusion furnace(s) by considering together the various real-life problem characteristics: Non-identical parallel diffusion furnaces, Machine eligibility restriction, Incompatible-job families, Job and/or resource related real time events, and Non-agreeable release time and due-date. In addition, due to the importance of on-time delivery this study deals with five due-date based scheduling objectives: Total weighted tardiness (TWT), Number of tardy jobs (NT), On time delivery (OTD) rate, Total earliness and lateness (TE/L) and Maximum lateness (Lmax) as a single objective as well as multi objectives. Here, the multi objectives are
developed, considering all the five due-date based scheduling objectives in a linear form by randomly assigning equal and unequal weights to each of the due-date based single objectives considered in this study. With these, the main objective of this thesis is to study the impact of job and/or resource related real time events (JR-RTE) on the relative efficiency of the proposed dynamic scheduling algorithms for diffusion furnace(s) while optimizing each of the due-date based scheduling objectives considered in this study.
The research problem considered in this study is decomposed into five phases. From the analysis of the literature, it is observed that, there is no earlier study has the mathematical models for dynamic scheduling (DS) of diffusion furnaces to optimize all the due-date based scheduling objectives, considered in this study. Due to this, in the first phase, fourteen (0-1) mixed integer linear programming (MILP) models are proposed for DS of diffusion furnaces (seven models for DS of single diffusion furnace and seven models for DS of non-identical parallel diffusion furnaces) to optimize the due-date based single objectives: TWT, NT, OTD rate, TE/L, and Lmax and multi objectives: MO1 and MO2. All the proposed (0-1) MILP models are demonstrated for its workability by developing a suitable numerical example, LINGO set code (which generates each of the proposed (0-1) MILP model for any given data), and solving using LINGO solver. Further, based on the analysis of the literature a suitable experimental design is proposed and generated 15 small-scale test data. The computational complexity of each of the proposed (0-1) MILP models is discussed empirically by solving 15 small-scale test data.
Due to the computational intractability of the proposed (0-1) MILP models for DS of diffusion furnaces, the second phase of the research focuses on a simple alternative approach based on dispatching rules, as the analysis of the literature reveals that dispatching rules are heavily used in the SM industry. However, there is no study in the literature presenting a comparative analysis of various dispatching rules particularly due-date based dispatching rules (DDR) for DS of diffusion furnace(s) to optimize various due-date based scheduling objectives. Accordingly, in the second phase, this study proposes a simple Greedy Algorithm (GA) based on DDR (called as GA-DDR) for Dynamic Scheduling of Single Diffusion Furnace (DS-SDF). Further, this study proposes twenty variants of GA-DDR considering various due-date based dispatching rules such as Earliest Due-Date, Flow Due-Date, Operational Due-Date, Modified Operational Due-Date,
Critical Ratio, Minimum Slack First, Cost OVER Time, ten versions of Apparent Tardiness Cost (ATC) [including a new ATC rule proposed in this study] & five versions of Batch Apparent Tardiness Cost (BATC) [including a new BATC rule proposed in this study] for DS-SDF. All these twenty variants of GA-DDR are implemented in Turbo C. An experimental design is proposed in this phase for generating large-scale test data. Accordingly, 270 large-scale problem instances (representing 27 problem configurations and 10 instances per configurations) are generated. With these, a series of computational experiments are carried out to understand the relative efficiency of the twenty proposed variants of GA-DDR as follows:
The efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives considered in this study is analysed in comparison with optimal objective function value obtained from the corresponding (0-1) MILP models for 15 small-scale problem instances using the standard performance measures: Average Relative Percentage Deviation (ARPD) and Maximum Relative Percentage Deviation (MRPD).
Further, for each of the 270 problem instances the efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives is analysed in comparison with estimated objective function value, which is computed by giving the twenty feasible solutions obtained for each instances as input to Weibull distribution, (i) empirically using the performance measures: ARPD, MRPD, Integrated Rank (IRANK), & Global comparison based on Worst Solution (GCWS), and (ii) statistically by using the performance measures: Mean, Median, and 95% confidence interval. From the overall analysis, at the end of the second phase of the study, six efficient variants of GA-DDR among the twenty proposed variants of GA-DDR are identified for DS-SDF and discussed the insights for their better performance. In these six efficient variants of GA-DDR, two variants of GA-DDR uses the new ATC rule and/or BATC rule proposed by the author of this thesis.
The second phase of the research considers only dynamic arrival of jobs in all the twenty variants of GA-DDR. But, in the real-life various unexpected job related real time events: rush job, due-date change, early/late arrival of job, change in job priority, and job cancellation and/or resource related real time events: machine breakdown, operator illness, tool failure, shortage of
material, and defective material will occur in addition to the dynamic arrival of jobs. From the literature, it is observed that, all the studies in the dynamic scheduling of diffusion furnaces consider only future arrival of jobs and no study considering real time events. Further, to the best of our knowledge, the research studies on discrete processing machines develop various rescheduling algorithm or modify the existing algorithm whenever real time events occur while taking the scheduling decision. However, due to the longest operation time requirements at diffusion furnace and the computerized tracking system in the shop floor of wafer fab, we strongly propose a research hypothesis that modifying appropriately the work-in-process (WIP) data and/or the availability time of the corresponding diffusion furnace(s) for next scheduling depending upon the occurrence of job and/or resource related real time events respectively by utilizing the existing computerized tracking system in the shop floor is sufficient, and changing any proposed efficient algorithms for DS-SDF is not required. This hypothesis is proved both empirically and statistically in the third phase of this research, considering the twenty proposed variants of GA-DDR for DS-SDF and the proposed experimental design.
Accordingly, this study propose a formal researchable hypothesis that there is no impact of JR-RTE on the relative efficiency of the twenty proposed variants of GA-DDR for DS-SDF while optimizing each of the due-date based scheduling objectives considered in this study. For testing the proposed hypothesis, this study proposed adjusted GA-DDR (with JR-RTE) for each of the proposed GA-DDR, in which there is step to update the WIP data if job related event occurs, and/or the next available time of corresponding diffusion furnace(s) for scheduling the same if resource related event occurs, before finalizing the scheduling decision.
Each of the 270 large-scale problem instances generated using the proposed experimental design is solved by each of the 20 adjusted variants of GA-DDR (with JR-RTE). The comparison on the relative efficiency of each of the 20 proposed variants of GA-DDR and adjusted GA-DDR (with JR-RTE) is carried out using the performance measures: ARPD and MRPD [that is, ARPD(GA-DDR) vs. ARPD(adjusted GA-DDR with JR-RTE), and MRPD(GA-DDR) vs. MRPD(adjusted GA-DDR with JR-RTE)] while optimizing each of the seven scheduling objectives considered in this study. The empirical analysis of the comparisons reveals that there is no change in the relative efficiency of each of the 20 proposed variants of GA-DDR and the corresponding 20
adjusted variants of GA-DDR (with JR-RTE) while optimizing each of the scheduling objectives considered in this study. Further, this study proved the proposed hypothesis statistically by conducting the Spearman‘s rank order correlation between each of the 20 variants of GA-DDR and adjusted GA-DDR (with JR-RTE) for DS-SDF while optimizing each of the seven due-date based scheduling objectives considered in this study. From the empirical and statistical analyses carried out in the third phase of the study indicated that, no need to adjust the proposed variants of GA-DDR for any occurrences of real time events for obtaining efficient schedule.
The SM industry normally would have more than one non-identical diffusion furnaces and that too in parallel. Due to some technical reasons, some jobs are processed only in specific diffusion furnace(s) available in the shop floor (this is called as machine eligibility restriction in scheduling theory). Hence, the impact of JR-RTE on the dynamic scheduling (DS) of non-identical parallel diffusion furnaces (NPDF) with machine eligibility restriction (MER) is addressed in the fourth phase of this study.
In the fourth phase of the research study, the twenty proposed variants of GA-DDR for DS-SDF extended appropriately for DS-NPDF with MER [called as Extended GA-DDR (EGA-DDR)]. Further, a few new problem parameters required for NPDF with MER are identified from the literature and extended the proposed experimental design and generated 270 problem instances for representing NPDF with MER. For testing the proposed hypothesis on the impact of JR-RTE on DS-NPDF with MER, exactly the similar research processes carried out for comparing GA-DDR vs. adjusted GA-DDR (with JR-RTE) is followed for comparing EGA-DDR vs. adjusted EGA-DDR (with JR-RTE). Both empirical and statistical analyses clearly proved that there is no impact of JR-RTE on the relative efficiency of the twenty variants of EGA-DDR for DS-NPDF with MER while optimizing each of the due-date based scheduling objectives considered in this study and no need to adjust the variants of EGA-DDR for any occurrences of real time events for obtaining efficient schedule.
So far, the study addressed the development of efficient GA-DDR and EGA-DDR for DS-SDF and DS-NPDF with MER respectively and studied the impact of JR-RTE on the relative efficiency of these proposed GA-DDR and EGA-DDR.
Now, in the final phase of the research study, the impact of JR-RTE on the meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), one at a time, for DS-SDF while minimizing TWT are studied. Accordingly, the required parameters for these two meta heuristics are identified from the literature and the meta heuristics: SA and TS, considering each of the six solutions obtained from the six efficient variants of GA-DDR respectively as initial solution are implemented. From the analysis of the solutions obtained, for each of the 270 problem instances, from each of the six efficient variants of GA-DDR and from each of the meta heuristics: SA and TS, it appears that the six efficient proposed variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution.
Further, to study the impact of JR-RTE on meta heuristics: SA and TS, this study considers (a) six solutions obtained from each of the six efficient variants of GA-DDR for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics, and
(b) six solutions obtained from each of the six adjusted variants of GA-DDR (with JR-RTE) for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics. For each of the meta heuristics, these two sets of final solutions, obtained for each of the 270 problem instances, are compared empirically and statistically, based on various performance measures considered in this study, and proved the research hypothesis defined in this study.
The major research contributions of this study are as follows
- By analyzing the literature on scheduling diffusion furnaces and the real-life situation in scheduling diffusion furnaces, a new research problem on dynamic scheduling (DS) of diffusion furnaces with incompatible-job families, machine eligibility restriction, non-agreeable release time and due-date, considering job and/or resource related real time events (JR-RTE) along with dynamic job arrival to optimize due-date based scheduling objectives: TWT, NT, OTD rate, TE/L, and Lmax as a single objective as well as multi objective was defined.
- Seven (0-1) MILP models for each of DS-SDF and DS-NPDF were proposed for optimizing each of the seven due-date based scheduling objectives considered in this study and the computational complexity was observed.
- Due to the computational complexity of the proposed (0-1) MILP models and the popularity of the dispatching rules in the semiconductor manufacturing industry, this study proposed and compared the twenty variants of (i) greedy algorithm based on due-date based dispatching rules (GA-DDR) for DS-SDF, and (ii) Extended GA-DDR for DS-NPDF with machine eligibility restriction (MER).
- The impact of JR-RTE on the twenty proposed variants of (a) GA-DDR for DS-SDF, and
(b) EGA-DDR for DS-NPDF with MER was studied and observed that modifying the data appropriately by utilizing the existing computerized tracking system available in the shop floor is sufficient and rescheduling or modifying the existing algorithms are not required when the occurrences of JR-RTE happens.
- Finally, single solution based meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), considering each of the six solution obtained from each of the six efficient variants of GA-DDR proposed in this study as initial solution respectively, were proposed for DS-SDF to minimize TWT. Performance analysis of the solution obtained from each of the six efficient variants of GA-DDR and from each of the meta heuristics were carried out and observed that efficient variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution. In addition, the impact of JR-RTE on the meta heuristics: SA and TS were studied and proved the research hypothesis proposed in this study.
Although, this study considers many real-life problem characteristics, there are certain limitations in this study. Though this study proposed mathematical model for DS-NPDF, the required additional constraint on Machine Eligibility is not considered in this study. Further, the impact of JR-RTE on the meta heuristics: SA and TS were studied considering only DS-SDF and not for DS-NPDF with MER. In addition to overcoming the limitations mentioned here, there are many immediate future research directions for the problem studied in this thesis such as proposing the greedy algorithms for scheduling diffusion operation along with upstream or downstream operation, and proposing population based meta heuristics for the research problem defined in this study. | en_US |
