# Linking Scheduling Criteria to Shop Floor Performance in Permutation Flowships
## 2 Background and Related Work
### Scheduling Criteria  
Undoubtedly, the most widely employed scheduling criterion is the makespan minimisation (usually denoted as \(C_{max}\)) or maximum flow time (see, e.g., [6] for a recent review on research in flowshop sequencing with makespan objective). Another important measure is the (total or average) total completion time or \(\sum C_{j}\). Although less employed in scheduling research than makespan, total completion time has also received a lot of attention, particularly during the last years. Just to mention a few recent papers, we note the contributions in [7; 8].  
An objective also considered in the literature is the minimisation of machine idle time, which can be defined in (at least) three different ways [9]:  
* The idle time, as well as the head and tail, of every single machine, i.e., the time before the first job is started on a machine and the time after the last job is finished on a machine, but the whole schedule has started on the first machine and has not been finished yet on the last machine, can be included into the idle time or not. In a static environment, including all heads and tails means that idle time minimisation is equivalent to minimisation of makespan (see, e.g., in [4]). This case would not have to be considered further.
* Excluding heads and tails would give an idle time within the schedule, implicitly assuming that the machines could be used for other tasks/jobs outside the current problem before and after the current schedule passes/has passed the machine. This definition of idle time is also known as \"core idle time\" (see, e.g., in [10; 11; 12]) and it has been used by [13] and by [14] in the context of a multicriteria problem. We denote this definition of idle time as \(\sum IT_{j}\).  
* Including machine heads in the idle time computation whereas the tails are not included means that the machines are reserved for the schedule before the first job of the schedule arrives but are released for other jobs outside the schedule as soon as the last job has left the current machine. In the following, we denote this definition as \(\sum{ITH_{j}}\). This definition is first encountered in [15] and in [16] and it has been used recently as a secondary criterion for the development of tie-breaking rules for makespan minimisation algorithms (see, e.g., [17; 18]).  
Figure 1 illustrates these differences in idle time computation for an example of two jobs on three machines. The light grey time-periods (IT and Head) are included in our idle time definition whereas the Tail is not. In the literature, an equivalent expression for heads and tails are Front Delay and Back Delay, respectively, see in [19] or [9].  
Finally, the last criterion under consideration is the Completion Time Variance (\(CTV\)). \(CTV\) was originally introduced by [20] in the computer scheduling context, where it is desirable to organise the data files in on-line computing systems so that the file access times are as uniform as possible. It has been subsequently applied in the manufacturing scheduling context as it is stated to be an appropriate objective for just-in-time production systems, or any other situation where a uniform treatment of the jobs is desirable (see, e.g., in [21; 22; 23; 24]). In the flow shop/job shop scheduling context, it has been employed by [25; 26; 27; 28; 29; 30; 31; 32].