# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 2 Previous Studies  
This section introduces the previous studies related to the scheduling problem considered in this study. First, the considered problem with urgent jobs can be classified as a multi-objective scheduling problem because two types of measures are combined, i.e., the makespan for normal jobs and total tardiness for urgent jobs. Recently, multi-objective scheduling problems are becoming popular as the manufacturing environments become more complex. [PERSON] et al. [6] proposed a self-adaptive differential evolution algorithm for minimizingthe maximum tardiness and makespan simultaneously in a flow shop with limited buffers. [PERSON] et al. [7] provided four metaheuristics for a flow shop that requires sequence-dependent setup times, with the objective of minimizing makespan and mean tardiness together, while [PERSON] et al. [8] considered a distributed reentrant permutation flow shop with sequence-dependent setup times for minimizing makespan, tardiness and production costs. Recently, multi-objective flow shop problems derived from energy consumption issues were considered in [9; 10; 11]. They suggested metaheuristic algorithms to minimize total energy consumption and makespan simultaneously. However, the combined objective of this problem is different from a typical multi-objective. In this study, the objective functions for the two classes are different because jobs are classified into two classes depending on their urgencies. On the contrary, in the typical multi-objective problems, two or more objectives are applied in common to all jobs. Therefore, this problem can be regarded as a multi-agent problem that is the special case of multi-objective problems [12]. In multi-agent problems, there are two or more agents, and each agent has a different objective function for its own jobs. If the different classes with different objectives are defined as different agents, this problem can be regarded as a multi-agent problem. Most studies on multi-agent scheduling considered problems for a single machine. [PERSON] et al. [13] developed algorithms for the multi-agent problem of a single system, considering the maximum delay, total weighted completion times and makespan for objective function. [PERSON] et al. [12] proposed algorithms for getting constrained optimal and pareto optimal solutions for the multi-agent on single machine problems and proved that the problem is NP-hard. [PERSON] et al. [14] studied the problem of two-agents on a single machine with the objective functions that the total completion time of the first agent is minimized and the number of tardy jobs of the second agent cannot exceed a predetermined number. [PERSON] et al. [15] proved that the same problem is NP-hard even if the number of tardy jobs for the second agent is limited to zero. [PERSON] et al. [16] proposed an algorithm for a two-agent problem on a single machine with the objective of minimizing the total weighted number of tardy jobs of each agent, and they also studied a multi-agent single machine problem with the max-form objective functions in [17]. [PERSON] et al. [18] studied a single machine with a two-agent problem in which each job has a linear deteriorated processing time. Additionally, polynomial time solution algorithms for a single-machine with two agents were suggested in [19; 20]. For a flow shop with multi agents, there have been only a few studies. [PERSON] et al. [12] studied a two-agent problem on a flowshop for minimizing makespan of jobs in each agent. [PERSON] et al. [21] developed a metaheuristic algorithm and a branch and bound algorithm to solve a two-agent problem in a two-machine flowshop. In addition, [PERSON] et al. [22] studied a flowshop problem with two agents where the objective of each agent is to minimize the number of tardy jobs and the total tardiness, respectively. [PERSON] et al. [23] studied three different flowshop problems with two agents and developed polynomial time solution algorithms for each problem.