permutation-flowshop 1.0.3

Package to facilitate studies about Permutation Flow Shop Scheduling Problem (PFSP)

Permutational Flowshop Library Documentation

Overview

The Permutational Flowshop Library was developed as a tool to assist analyses and studies involving the Permutational Flowshop Scheduling Problem (PFSP), a classic optimization topic in the context of Operations Research.

The main objective of the PFSP is to schedule a set of $n$ jobs on a set of $m$ machines, in the same sequence of machines, in which the jobs have identical ordering sequences on all machines (Ravetti et al., 2012).

This library provides, heuristic and metaheuristic methods that enable the creation of a schedule to process a set of $n$ jobs on $m$ machines. The metric used to determine the scheduling is the total time required to execute all the jobs on all machines (makespan).

Table of Contents

• Installation
• Functions
  • Reading an instance
  • Makespan
  • NEH
  • NEHT
  • Gantt Chart
  • Local Search
    • Local Search with the Swap First Improvement Strategy
    • Local Search with the Swap Best Improvement Strategy
  • Multi-start
  • GRASP

Installation

To install the package, run the command below:

 pip install permutation-flowshop 

Functions

Reading an instance

The package allows reading txt and csv files.

The required input data to run the methods are:

• Number of Jobs ($n$)
• Number of Machines ($m$)
• Processing Times (of each job in each machine)

This data must be organized according to the Taillard (1993) instances standard, as shown in the example below:

20 5
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94
79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77
16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40
66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31
58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28

The first line contains the number of jobs ($n$) and the number of machines ($m$), respectively. Lines 2 to m + 1 contain the job processing times of each job in each machine. In the example above, we have an instance with 20 jobs and 5 machines, and a 5x20 processing time matrix.

Reading a file in txt format:

#Usage Example

from pfsp.read_file import read_txt

file = "your_path/instance.txt"

number_jobs, number_machines, processing_times_array = read_txt(file)

To read a csv file the data must be separated by commas, as shown below:

54,83,15,71,77,36,53,38,27,87,76,91,14,29,12,77,32,87,68,94
79,3,11,99,56,70,99,60,5,56,3,61,73,75,47,14,21,86,5,77
16,89,49,15,89,45,60,23,57,64,7,1,63,41,63,47,26,75,77,40
66,58,31,68,78,91,13,59,49,85,85,9,39,41,56,40,54,77,51,31
58,56,20,85,53,35,53,41,69,13,86,72,8,49,47,87,58,18,68,28

Reading a file in csv format:

#Usage Example

from pfsp.read_file import read_csv

file = "your_path/instance.csv"

number_jobs, number_machines, processing_times_array = read_csv(file)

Makespan

The makespan function computes the completion time of a given sequence, i.e., the completion time of the last job (of the given sequence) in the last machine.

#Usage example
from pfsp.calculate_makespan import calculate_makespan

sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]

makespan = calculate_makespan(sequence, number_jobs, number_machines, processing_times_array)
print(f"Makespan = {makespan}")

NEH

The NEH function finds the sequence and the associated makespan following the logic of the NEH constructive heuristic (Nawaz et al., 1983).

#Usage example
from pfsp.NEH import NEH

sequence_NEH, makespan_NEH = NEH(number_jobs, number_machines, processing_times_array, show=False)

print(f"Sequence Obtained by the NEH: {sequence_NEH}")
print(f"Makespan Obtained by the NEH = {makespan_NEH}")

The parameter show is used to display the resulting information regarding the sequence found by the NEH heuristic and the associated makespan. The default value of the parameter is show = False, so nothing will be displayed. Only by setting show = True the information will be shown at the end of the execution.

NEHT

The NEHT function finds the sequence and the associated makespan following the logic of the NEHT constructive heuristic (Taillard, 1990). It is important to highlight that the difference between NEH and NEHT is that NEHT offers greater efficiency.

#Usage example
from pfsp.NEHT import NEHT

sequence_NEHT, makespan_NEHT = NEHT(number_jobs, number_machines, processing_times_array, show=False)

print(f"Sequence Obtained by the NEHT: {sequence_NEHT}")
print(f"Makespan Obtained by the NEHT = {makespan_NEHT}")

"The parameter show is used to display the resulting information regarding the sequence found by the NEH heuristic and the associated makespan. The default value of the parameter is show = False, so nothing will be displayed. Only by setting show = True the information will be shown at the end of the execution.

Gantt Chart

The library is capable of generating an interactive Gantt chart, displaying the start and end times of each job on each machine. The chart will be opened in your computer's browser.

#Usage example
from pfsp.gantt import gantt_chart

sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]

gantt_chart(number_jobs, number_machines, processing_times_array, sequence)

Local Search

Local Search with the Swap First Improvement

This function executes a local search on a given sequence of jobs, using the swap neighborhood operator, working under the first improvement strategy. The initialization of the makespan occurs from the value associated with the initial sequence.

  #Usage example
  from pfsp.calculate_makespan import calculate_makespan
  from pfsp.local_search import local_search_swap_first_improvement

  initial_sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]

  initial_makespan = calculate_makespan(initial_sequence, number_jobs, number_machines, processing_times_array)

  local_search_sequence, local_search_makespan = local_search_swap_first_improvement(number_jobs, number_machines, processing_times_array, initial_sequence, initial_makespan)

  print(f"Local Search Sequence : {local_search_sequence}")
  print(f"Local Search Makespan : {local_search_makespan}")

  

Local Search with the Swap Best Improvement

This function executes a local search on a given sequence of jobs, using the swap neighborhood operator, working under the best improvement strategy. The initialization of the makespan occurs from the value associated with the initial sequence.

  #Usage example
  from pfsp.calculate_makespan import calculate_makespan
  from pfsp.local_search import local_search_swap_best_improvement

  initial_sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]

  initial_makespan = calculate_makespan(initial_sequence, number_jobs, number_machines, processing_times_array)

  local_search_sequence, local_search_makespan = local_search_swap_best_improvement(number_jobs, number_machines, processing_times_array, initial_sequence, initial_makespan)

  print(f"Local Search Sequence : {local_search_sequence}")
  print(f"Local Search Makespan = {local_search_makespan}")

  

Multi-start

The function executes the multi-start metaheuristic, where the constructive phase involves a randomly generated sequence of $n$ jobs. This is followed by a local search that uses the swap operator in conjunction with the best improvement or the first improvement strategy. In the end, it will return the best sequence found, the value of the makespan associated with it , the number of starts executed, the running time of the algorithm, and the matrix with the completion times of each job in each machine.

Parameter	Description
number_jobs	Number of jobs
number_machines	Number of machines
processing_times_array	Matrix with the processing times of each job in each machine
starts	Integer number of starts of multi-start metaheuristic
ls	Local search strategy, with two options: ls=swapbi, which performs local search with the swap neighborhood operator using the best improvement strategy, or ls=swapfi, which performs local search with the swap neighborhood operator using the first improvement strategy.
logs	The logs can display the process of updating sequences and the makespan associated with each local search, where the solution found is improved (minimized) compared to previous solutions during the metaheuristic. To enable this feature, set the parameter to logs = True. If the user prefers not to monitor solution updates, the parameter should be initialized with logs = False.

Example involving Local Search with the Swap Best Improvement, bellow:

#Usage example
from pfsp.metaheuristics import multistart

best_sequence_multistart, best_makespan_multistart, iterations, elapsed_time, completion_time_matrix = multistart(number_jobs, number_machines, processing_times_array, starts = 10, ls='swapbi', logs=True)

Example involving Local Search with the Swap First Improvement, bellow:

#Usage example
from pfsp.metaheuristics import multistart

best_sequence_multistart, best_makespan_multistart, iterations, elapsed_time, completion_time_matrix = multistart(number_jobs, number_machines, processing_times_array, starts = 10, ls='swapfi', logs=True)

GRASP

This function executes the GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic (FEO and Resende, 1995) which uses a constructive approach based on the Restricted Candidate List, as detailed in Resende and Ribeiro (2019). The constructive phase is followed by a local search that utilizes the swap operator, applying either the best improvement strategy or the first improvement strategy. The function returns the best sequence found, the value of the makespan associated with it, the number of iterations executed, the running time of the algorithm, and the matrix of completion times of each job in each machine.

Parameter	Description
number_jobs	Number of jobs
number_machines	Number of machines
processing_times_array	Matrix with the processing times of each job in each machine
alpha	between 0 and 1
max_iterations	Integer number of iterations executed
ls	Local search strategy, with two options: ls=swapbi, which performs local search with the swap neighborhood operator using the best improvement strategy, or ls=swapfi, which performs local search with the swap neighborhood operator using the first improvement strategy.
logs	The logs can display the process of updating sequences and the makespan associated with each local search, where the solution found is improved (minimized) compared to previous solutions during the metaheuristic. To enable this feature, set the parameter to logs = True. If the user prefers not to monitor solution updates, the parameter should be initialized with logs = False.

An example involving a Local Search with the Best Improvement Strategy is provided bellow:

#Usage example
from pfsp.metaheuristics import grasp

best_sequence_grasp, best_makespan_grasp, iterations, elapsed_time, completion_time_matrix = grasp(number_jobs, number_machines, processing_times_array, alpha=0.5, max_iterations = 10, ls='swapbi', logs=True)

An example involving a Local Search with the First Improvement Strategy is provided bellow:

#Usage example
from pfsp.metaheuristics import grasp

best_sequence_grasp, best_makespan_grasp, iterations, elapsed_time, completion_time_matrix = grasp(number_jobs, number_machines, processing_times_array, alpha=0.5, max_iterations = 10, ls='swapfi', logs=True)

References

• RAVETTI, M. G.; RIVEROS, C.; MENDES, A.; RESENDE, M. G.; PARDALOS, P. M. Parallel hybrid heuristics for the permutation flow shop problem. Annals of Operations Research, Springer, v. 199, p. 269–284, 2012.
• NAWAZ, M.; ENSCORE, E. E.; HAM, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, v. 11, n. 1, p. 91–95, 1983. ISSN 0305-0483. Access: https://www.sciencedirect.com/science/article/pii/0305048383900889.
• TAILLARD, Scheduling instances: benchmarks for basic scheduling problems. 1993. 30 set. 2024. Access: http://mistic.heig-vd.ch/taillard/problemes.dirordonnancement.dir/ordonnancement.html.
• TAILLARD, E. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65-74. 1990. Access: https://doi.org/10.1016/0377-2217(90)90090-X
• FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, n. 2, p. 109–133, 1995.
• RESENDE, Maurício G. C.; RIBEIRO, Celso C. Greedy Randomized Adaptive Search Procedures: Advances and Extensions. In: GENDREAU, Michel; POTVIN, Jean-Yves (Eds.). Handbook of metaheuristics. 3. ed. Cham: Springer, 2019. v. 272, p. 169–220.