## 5 Applications
### Scheduling  
As mentioned in Introduction, the motivation of this study was inspired by trying to solve a kind of _open shop_ scheduling problem that is concerned with setup time among different types of machines [17]. Here, setup time means delay time that occurs when we arrange the processing route (or path) of a job from one type of machine to another type of machine. In scheduling problems, if the paths of jobs are fixed beforehand, and are the same for all jobs, it is called a _flow-shop_[27]; on the other hand, if the paths of jobs are not given in advance, but chosen by the scheduler, it is called an _open-shop_[28]. What we are trying to solve is an open shop scheduling problem that comprised a set of J jobs, {1, 2,..., J}, and \(n\) machines with two types of A and B. That is, every job must pass through all \(n\) machines for each machine once. Assume that \(n_{1}\) and \(n_{2}\) be the number of machines of type A and B respectively, and that \(n=n_{1}+n_{2}\). Now, let \(\pi_{{}_{j}}=\pi_{{}_{j1}}\pi_{{}_{j2}}\cdots\pi_{{}_{jn}}\) be a path of job \(j\) where \(\pi_{{}_{jk}}\), for all \(k\in\{1,2,\cdots,n\}\), can be a symbol of \"A\" or \"B\" that stands for the \(k^{\rm th}\) operation of job \(j\) is processed by a machine of type A or B, respectively. To be a valid path, obviously, in a path \(\pi_{{}_{j}}\) of a job \(j\) there must have \(n_{1}\) A's, and \(n_{2}\) B's. For example, if \(n_{1}=4\) and \(n_{1}=6\) then \(\pi_{{}_{j}}=\) AAABBABBBB and \(\pi_{{}_{j}}=\) AABBBABBBA can be two feasible paths of  
Figure 2: Running Time of **Permute\({}^{+}\)**_vs._ Problem Size. a job \(j\). It is trivial that there are totally \(\dfrac{n!}{n_{!}n_{2}! }\) different feasible paths for a job. If we assume that there are no two jobs with the same path, there are totally \(\left(\dfrac{n!}{n_{!}!n_{2}! }\right)\) different feasible schedules can be chosen by the scheduler. How to choose a schedule depends on what objective the scheduler aims at. One widely used objective is to minimize the make span, the time needed to complete all jobs. Traditionally, it is common to assume that, when its previous operation has been completed by a machine, a job is immediately available to be processed by another machine. However, in practice, there is often a significant time delay between the completion of an operation and the start of the next operation of the same job. Furthermore, in some cases, the processing times might be negligible compare to the delay times. Therefore, they have a small influence on the make span [29]. Several real world applications can be found in [30]. The _open shop_ scheduling problem with time delays was first introduced in [31], and shown to be NP-hard even for two machines and identical time delays. Let \(d\) stand for the delay times needed to transfer a job from a machine of type A (or B) to a machine of type B (or A), and \(D_{j}\) stand for the total delay times needed for a job \(j\) to complete its path. Here, we assume that transfer a job between two machines of the same type does not cause any delay time. Without loss of generality, we can set delay times \(d=1\). Therefore, for two paths such as \(\pi_{1}=\) AAABBABBBB and \(\pi_{2}=\) AABBBABBBA, we have \(D_{1}=3\) and \(D_{2}=4\). Our objective is to minimize the total delay times of all jobs, that is, to minimize \(\sum_{j=1}^{j=3}D_{j}\). Since a path of a job can be viewed as a permutation of a two-item {A\({}^{\pi_{1}}\), B\({}^{\pi_{2}}\)} multiset, the feasible paths of a job can be obtained by an algorithm that can generate all feasible permutations of this multiset. The question is how to choose J permutations, from the \(\dfrac{n!}{n_{!}!n_{2}! }\) feasible permutations, for these J jobs such that \(\sum_{j=1}^{j=1}D_{j}\) is minimized. Note that in the multiset permutation, we call there is a _turn_ if two consecutive elements are belonging to two different items. That is, a _turn_ occurs if we transfer a job from a machine of type A (or B) to a machine of type B (or A).