## 2 Related Work  
In manufacturing systems, scheduling is about the allocation of resources to operations over time to somehow optimize the efficiency of the corresponding system. Quite interestingly, because of their complexity, scheduling problems have been among the first categories of problems that have promoted the development of the notion of NP-completeness [5]. The Flow-shop Scheduling Problem (FSP), in which jobs should pass all machines in the same order, is one of the easy-to-state but hard-to-solve problems in scheduling. Because of these contrasting features, the FSP is one of the first problems in scheduling which captured the attention of pioneers in scheduling [4; 6], and later became an attractive topic for a significant number of researchers. Interestingly, one of the most elegant procedures in the area of algorithmic design is an efficient exact algorithm [4] that has been presented for the two special cases of this problem, which are a two-machine problem and a restricted case of the three-machine problem. Although this algorithm has been extended [6; 7] to tackle some less restricted cases of the three-machine problem, it has never been extended to solve problems with a larger number of machines to optimality. Several variations and extensions of the FSP, with multiple objective function criteria, have been studied in the literature [8; 9; 10]. Among the variants of the FSP, the Permutation Flow-shop Scheduling Problem (PFSP), in which jobs have the same sequence on all machines, plays a key role. The PFSP best suits multi-stage production systems in which conveyor belts are used to perform material handling between machines. Both the FSP and the PFSP have shown to be NP-Hard [11; 12]. An interesting variant of the PFSP is the distributed permutation flow shop scheduling problem (DPFSP) which has been studied in [13], and, in [14], energy consumption considered as one of its multi-objective criteria. The rest of this section briefly surveys the related literature with a focus on the PFSP. Extensive literature surveys on the early efficient algorithms presented for the FSP can be found in [15; 16]. A more recent review and classification of heuristics for the PFSP has been presented in [17]. In the proposed framework of [17], heuristics are analyzed in the three phases of (i) index development, (ii) solution construction and (iii) solution improvement. In the following, some related work is briefly reviewed. The most related method is [PERSON]'s method that because of the complete dependence of the RDIS on it, this method will be described as part of the RDIS in Section 4. The [PERSON] method developed in [18] can be considered as another related work. The author has not provided any reference to [PERSON]'s paper but has mentioned that the rationale behind the development of the procedure is to minimize the makespan based on the notion of the lower bound of the single machine problem, which is obtained by the head time plus its total processing times plus its tail time. It is these heads and tails that the [PERSON] algorithm tries to minimize. Based on advancing [PERSON]'s index method, an algorithm has been presented in [19] which works based on a slope matching mechanism. First, assuming that only one job exists, the starting time and ending time of each job on each machine is calculated and, by running the regression, a starting slope and an ending slope are calculated for each job. The first method, with which they have compared their two techniques, is the method presented in [20], that finds the actual slope of jobs. For calculating this actual slope, simply the regression is run for each job. The other method that they have compared with their two methods is the method based on the priority presented by [21], and obtained based on [PERSON]'s rule. In comparing these four methods with one another, they found the following ranking (i) TSP-approximation, (ii) slope-matching mechanism, (iii) [PERSON]'s method, and (iv) [PERSON]'s method.