Consider a classic problem in the literature, the Permutation Flowshop (PFSP) in which a set of J tasks consists of a set of tasks (1, 2, ..., j) to be processed on a set M of machines (1, 2, ..., m). In the PFSP, all tasks are processed serially on multiple machines in the same order. Moreover, each job can be processed on a single machine at a time and each machine can process only one job at a time, respectively. In addition, all operations cannot be interrupted, and setup times are included in the processing times and are independent of sequencing decisions. The scheduling problem is to find a task sequence that optimizes a certain performance criterion, in this case, the total time to complete all tasks (makespan).

We are given the following standard problem in the literature Ta001 (Taillard, 1993), which is a 20-task, 5-machine problem.

According to this problem, the processing time of job 3 (J3) on machine 5 (M5) is for example 20 units of time. Questions:

• Calculate the number of possible solutions to the problem
• Explain which type of algorithm best suits its solution (exact, heuristics, metaheuristics).
• Choose an algorithm to solve and develop it in the language programming language of your choice.
• List the optimal solution you found and the makespan (total time completion time) of this solution*.

• given that BKS = 1278 where BKS -> Best Known Solution

The solution we got is 1278 in around 1 second, which is the same as the Best Known Solution (BKS) for this problem. The algorithm used to solve this problem is a hybrid algorithm that combines the Genetic Algorithm (GA) with the Tabu Search (TS) algorithm.

The code is implemented in Python and can be found in the following link: Permutation Flowshop Solution Implementation

The analytical explanation of the code can be found in the following link: Permutation Flowshop Solution Implementation Explanation