# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 1 Introduction  
This study deals with a scheduling problem in a flow shop with urgent jobs and limited waiting times. _Urgent jobs_ refer to jobs that must be processed faster due to higher urgency than normal jobs. _Limited waiting time_ is to limit the time that a job completed on the first machine waits to start the next process on the second machine. These two scheduling requirements are very common in semiconductor manufacturing processes. In general, semiconductor manufacturing systems are operated in high-variety small-volume production and make-to-order policies. Nowadays, because the semiconductor foundry market is growing rapidly, customer order management and fast demand response capability are considered as very important competitive factors. To cope with this environment, jobs are classified into two (or more) groups depending on the urgencies of customer orders, i.e., a normal job and an urgent job. In this case, for normal jobs, a schedule is established with the objective of minimizing the maximum completion time (makespan) to raise throughput rate. However, urgent jobs are required to start processing as early as possible when they arrive at workstations. To accomplish this, each urgent job has a calculated due date, assuming that it is processed through all steps without waiting immediately upon arrival. That is, the due date on each step is equal to the earliest possible completion time. Based on this assumption, the objective of minimizing total tardiness can be considered as the scheduling measure for the urgent jobs. If normal and urgent jobs are required to be scheduled together on the same machine or shop, the scheduling measure is treated as a multi-objective because the makespan for normal jobs and total tardiness for urgent jobs are combined. Especially in semiconductor manufacturing, the urgent jobis called _hot-lot_ and managed with a high priority. The urgent jobs can be found in many make-to-order manufacturing systems besides semiconductors. In general, prototypes, samples, and lots to make up for the defective products are regarded as urgent jobs, and such jobs account for 30-50% of all jobs [1]. So, it is essential to make an effective and efficient schedule while considering the urgent jobs. Semiconductor manufacturing has many chemical processes. To prevent quality problems of wafer lots caused by the characteristics of chemical processes, waiting time constraints are required between consecutive processes (or stages). For example, the waiting time constraints are set between operations in etch-oxidation-deposition-diffusion work areas [2]. If the chemical treatment is effective only within a certain period of time, the chemically treated wafer lot has to be entered into the next process before it exceeds the limited time. In the case that the first process of two consecutive processes is such a chemical process, the limited waiting time constraint is applied between the two processes. Moreover, wafers are naturally oxidized if wafers are left in the air for a certain period of time [3]. On the other hand, the waiting time constraint is also required to reduce the possibility of contamination that causes quality degradation. When the surface of a wafer is exposed to air for a long time before the next process, impurities such as particles may sit on the surface, which can cause a serious quality problem. To prevent this problem, the exposure time is limited by setting the waiting time constraint. A representative example with the waiting time constraint is a two-stage flow shop of clean-diffusion consecutive steps. In order to prevent the above problems, the waiting times between the clean and diffusion processes are limited by the constraint. If a wafer exceeds the constrained waiting time, the cleaning process is reworked, or if contamination is severe, the wafer is scrapped. The rework and scrap degrade productivity and cause losses of management. Therefore, the waiting time constraint should be considered for the flow shops where the above quality problems are likely to occur.