| Name | permutation-flowshop JSON |
| Version |
1.0.2
JSON |
| download |
| home_page | None |
| Summary | Package to facilitate studies about Permutation Flow Shop Scheduling Problem (PFSP) |
| upload_time | 2024-10-21 19:13:39 |
| maintainer | None |
| docs_url | None |
| author | Bruno, Raphael |
| requires_python | >=3.10 |
| license | None |
| keywords |
permutation
flowshop
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# 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 jobs on a set of machines, where each job is processed on each machine in the same order as it was processed on the previous machine (Ravetti et al., 2012)
This library provides, among other resources, 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 n jobs on all m machines (makespan).
## Table of Contents
- [Installation](#installation)
- [Functions](#functions)
- [Reading a File](#read_file)
- [Makespan](#makespan)
- [NEH](#neh)
- [NEHT](#neht)
- [Gantt Chart](#gantt_chart)
- [Local Search](#local_search)
- [Local Search with the Swap First Improvement Strategy](#local_search_swap_first_improvement)
- [Local Search with the Swap Best Improvement Strategy](#local_search_swap_best_improvement)
- [Multi-start](#multistart)
- [GRASP](#grasp)
## [Installation]
To install the package, run the command below:
<pre><code> pip install permutation-flowshop </code></pre>
## [Functions]
### Reading a File
The package allows reading files with processing times in txt and csv formats.
For reading the file in txt format, it must be formatted according to the Taillard (1993) instances standard, as shown in the example below:
20 5 <br>
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94 <br>
79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77 <br>
16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40 <br>
66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31 <br>
58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28 <br>
The number of jobs should be placed in the first position, followed by the number of machines in the second position, In this example, 20 jobs and 5 machines. The processing time matrix has the number of columns representing the number of tasks and the number of rows representing the number of machines, forming the processing time of each job on each machine.
Reading a file in txt format:
<pre><code>
#Usage Example
from pfsp.read_file import read_txt
file = "your_path/instance.txt"
number_jobs, number_machines, processing_times_array = read_txt(file)
</code></pre>
For reading the file in csv format, it must be formatted, as shown below:
54,83,15,71,77,36,53,38,27,87,76,91,14,29,12,77,32,87,68,94 <br>
79,3,11,99,56,70,99,60,5,56,3,61,73,75,47,14,21,86,5,77 <br>
16,89,49,15,89,45,60,23,57,64,7,1,63,41,63,47,26,75,77,40 <br>
66,58,31,68,78,91,13,59,49,85,85,9,39,41,56,40,54,77,51,31 <br>
58,56,20,85,53,35,53,41,69,13,86,72,8,49,47,87,58,18,68,28 <br>
A file in CSV format separated by commas must be provided. The processing time matrix has the number of columns representing the number of jobs and the number of rows representing the number of machines, forming the processing time of each job on each machine.
Reading a file in csv format:
<pre><code>
#Usage Example
from pfsp.read_file import read_csv
file = "your_path/instance.csv"
number_jobs, number_machines, processing_times_array = read_csv(file)
</code></pre>
### Makespan
The makespan function will calculate the completion time of a given sequence. This function can be used to calculate partial sequences,
but it will be necessary to specify the number of jobs and the number of machines according to the dimensions of the processing time matrix.
<pre><code>
#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}")
</code></pre>
### NEH
The NEH function will be able to find the sequence and the associated makespan following the logic of the NEH constructive heuristic (Nawaz et al., 1983).
<pre><code>
#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}")
</code></pre>
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` will the information be shown at the end of the execution.
### NEHT
The NEHT function will be able to find 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.
<pre><code>
#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}")
</code></pre>
"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` will the information 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.
<pre><code>
#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)
</code></pre>
### Local Search
#### Local Search with the Swap First Improvement
This function allows the execution of 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.
<pre><code>
#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}")
</code></pre>
#### Local Search with the Swap Best Improvement
This function allows the execution of 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.
<pre><code>
#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}")
</code></pre>
### Multi-start
The function executes the multi-start metaheuristic, where the constructive phase involves a randomly generated sequence of number_jobs. This is followed by a local search that uses the swap operator in conjunction with the best improvement or first improvement strategy. In the end, it will return the best sequence found, the best makespan associated, the number of starts executed, execution time, and the matrix with the completion times of each job in the each machine.
| Parameter | Description |
|------------|-------|
| number_jobs | Number of jobs |
| number_machines | Number of machines |
| processing_times_array | Matrix with processing times for each job of 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. It is also possible to perform local search with the swap using the first improvement strategy. In this case, just initialize the parameter with `ls=swapfi`.|
| 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:
<pre><code>
#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)
</code></pre>
Example involving Local Search with the Swap First Improvement, bellow:
<pre><code>
#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)
</code></pre>
### GRASP
The function implements the GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic (FEO and Resende, 1995) using a constructive approach based on the Restricted Candidate List, as detailed in Resende and Ribeiro (2019). This library approach includes a constructive phase followed by a local search that utilizes the swap operator, applying either the best improvement strategy or the first improvement strategy. Ultimately, the function returns the best sequence found, the best associated makespan, the number of iterations executed, the execution time, and the matrix of completion times for each task on each machine.
Parameter | Description |
|------------|-------|
| number_jobs | Number of jobs |
| number_machines | Number of machines |
| processing_times_array | Matrix with processing times for each job of 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. It is also possible to perform local search with the swap using the first improvement strategy. In this case, just initialize the parameter with `ls=swapfi`.|
| 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:
<pre><code>
#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)
</code></pre>
Example involving Local Search with the Swap First Improvement, bellow:
<pre><code>
#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)
</code></pre>
## 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.
Raw data
{
"_id": null,
"home_page": null,
"name": "permutation-flowshop",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": "permutation flowshop",
"author": "Bruno, Raphael",
"author_email": "bruno.development3@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/f5/b3/befa21efafb46d45820cefc45bf0ff098e02ae4a07153dee39f35f68b7b0/permutation_flowshop-1.0.2.tar.gz",
"platform": null,
"description": "# Permutational Flowshop Library Documentation\n\n## Overview\nThe 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.\n\nThe main objective of the PFSP is to schedule a set of jobs on a set of machines, where each job is processed on each machine in the same order as it was processed on the previous machine (Ravetti et al., 2012)\n\nThis library provides, among other resources, 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 n jobs on all m machines (makespan).\n\n\n## Table of Contents\n- [Installation](#installation)\n- [Functions](#functions)\n - [Reading a File](#read_file)\n - [Makespan](#makespan)\n - [NEH](#neh)\n - [NEHT](#neht)\n - [Gantt Chart](#gantt_chart)\n - [Local Search](#local_search)\n - [Local Search with the Swap First Improvement Strategy](#local_search_swap_first_improvement)\n - [Local Search with the Swap Best Improvement Strategy](#local_search_swap_best_improvement)\n - [Multi-start](#multistart)\n - [GRASP](#grasp)\n\n## [Installation]\nTo install the package, run the command below:\n<pre><code> pip install permutation-flowshop </code></pre>\n\n## [Functions]\n### Reading a File\nThe package allows reading files with processing times in txt and csv formats.\n\nFor reading the file in txt format, it must be formatted according to the Taillard (1993) instances standard, as shown in the example below:\n\n\n\n20 5 <br>\n54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94 <br>\n79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77 <br>\n16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40 <br>\n66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31 <br>\n58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28 <br>\n\nThe number of jobs should be placed in the first position, followed by the number of machines in the second position, In this example, 20 jobs and 5 machines. The processing time matrix has the number of columns representing the number of tasks and the number of rows representing the number of machines, forming the processing time of each job on each machine.\n\nReading a file in txt format:\n<pre><code>\n#Usage Example\n\nfrom pfsp.read_file import read_txt\n\nfile = \"your_path/instance.txt\"\n\nnumber_jobs, number_machines, processing_times_array = read_txt(file)\n\n</code></pre>\n\n\nFor reading the file in csv format, it must be formatted, as shown below:\n\n54,83,15,71,77,36,53,38,27,87,76,91,14,29,12,77,32,87,68,94 <br>\n79,3,11,99,56,70,99,60,5,56,3,61,73,75,47,14,21,86,5,77 <br>\n16,89,49,15,89,45,60,23,57,64,7,1,63,41,63,47,26,75,77,40 <br>\n66,58,31,68,78,91,13,59,49,85,85,9,39,41,56,40,54,77,51,31 <br>\n58,56,20,85,53,35,53,41,69,13,86,72,8,49,47,87,58,18,68,28 <br>\n\nA file in CSV format separated by commas must be provided. The processing time matrix has the number of columns representing the number of jobs and the number of rows representing the number of machines, forming the processing time of each job on each machine.\n\n\n\nReading a file in csv format:\n<pre><code>\n#Usage Example\n\nfrom pfsp.read_file import read_csv\n\nfile = \"your_path/instance.csv\"\n\nnumber_jobs, number_machines, processing_times_array = read_csv(file)\n\n</code></pre>\n\n\n### Makespan\n\nThe makespan function will calculate the completion time of a given sequence. This function can be used to calculate partial sequences,\n but it will be necessary to specify the number of jobs and the number of machines according to the dimensions of the processing time matrix.\n\n<pre><code>\n#Usage example\nfrom pfsp.calculate_makespan import calculate_makespan\n\nsequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]\n\nmakespan = calculate_makespan(sequence, number_jobs, number_machines, processing_times_array)\nprint(f\"Makespan = {makespan}\")\n\n</code></pre>\n\n### NEH\nThe NEH function will be able to find the sequence and the associated makespan following the logic of the NEH constructive heuristic (Nawaz et al., 1983).\n\n<pre><code>\n#Usage example\nfrom pfsp.NEH import NEH\n\nsequence_NEH, makespan_NEH = NEH(number_jobs, number_machines, processing_times_array, show=False)\n\nprint(f\"Sequence Obtained by the NEH: {sequence_NEH}\")\nprint(f\"Makespan Obtained by the NEH = {makespan_NEH}\")\n\n</code></pre>\n\nThe parameter `show` is used to display the resulting information regarding the sequence found by the NEH heuristic and the associated makespan.\nThe default value of the parameter is `show = False`, so nothing will be displayed. Only by setting `show = True` will the information be shown at the end of the execution.\n\n### NEHT\n\nThe NEHT function will be able to find the sequence and the associated makespan following the logic of the NEHT constructive heuristic (Taillard, 1990).\nIt is important to highlight that the difference between NEH and NEHT is that NEHT offers greater efficiency.\n\n<pre><code>\n\n#Usage example\nfrom pfsp.NEHT import NEHT\n\nsequence_NEHT, makespan_NEHT = NEHT(number_jobs, number_machines, processing_times_array, show=False)\n\nprint(f\"Sequence Obtained by the NEHT: {sequence_NEHT}\")\nprint(f\"Makespan Obtained by the NEHT = {makespan_NEHT}\")\n\n</code></pre>\n\n\"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` will the information be shown at the end of the execution.\n\n### Gantt Chart\nThe 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.\n\n<pre><code>\n\n#Usage example\nfrom pfsp.gantt import gantt_chart\n\nsequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]\n\ngantt_chart(number_jobs, number_machines, processing_times_array, sequence)\n\n\n</code></pre>\n\n### Local Search\n #### Local Search with the Swap First Improvement\n\n This function allows the execution of 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.\n <pre><code>\n\n #Usage example\n from pfsp.calculate_makespan import calculate_makespan\n from pfsp.local_search import local_search_swap_first_improvement\n\n initial_sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]\n\n initial_makespan = calculate_makespan(initial_sequence, number_jobs, number_machines, processing_times_array)\n\n local_search_sequence, local_search_makespan = local_search_swap_first_improvement(number_jobs, number_machines, processing_times_array, initial_sequence, initial_makespan)\n\n print(f\"Local Search Sequence : {local_search_sequence}\")\n print(f\"Local Search Makespan : {local_search_makespan}\")\n\n </code></pre>\n\n #### Local Search with the Swap Best Improvement\n\n This function allows the execution of 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.\n\n <pre><code>\n\n #Usage example\n from pfsp.calculate_makespan import calculate_makespan\n from pfsp.local_search import local_search_swap_best_improvement\n\n initial_sequence = [14, 7, 11, 3, 8, 5, 0, 9, 2, 15, 4, 16, 12, 18, 10, 1, 13, 17, 19, 6]\n\n initial_makespan = calculate_makespan(initial_sequence, number_jobs, number_machines, processing_times_array)\n\n local_search_sequence, local_search_makespan = local_search_swap_best_improvement(number_jobs, number_machines, processing_times_array, initial_sequence, initial_makespan)\n\n print(f\"Local Search Sequence : {local_search_sequence}\")\n print(f\"Local Search Makespan = {local_search_makespan}\")\n\n </code></pre>\n\n### Multi-start\n\nThe function executes the multi-start metaheuristic, where the constructive phase involves a randomly generated sequence of number_jobs. This is followed by a local search that uses the swap operator in conjunction with the best improvement or first improvement strategy. In the end, it will return the best sequence found, the best makespan associated, the number of starts executed, execution time, and the matrix with the completion times of each job in the each machine.\n\n| Parameter | Description |\n|------------|-------|\n| number_jobs | Number of jobs |\n| number_machines | Number of machines |\n| processing_times_array | Matrix with processing times for each job of each machine|\n| starts | Integer number of starts of multi-start metaheuristic|\n| ls | Local search strategy, with two options: `ls=swapbi`, which performs local search with the swap neighborhood operator using the best improvement strategy. It is also possible to perform local search with the swap using the first improvement strategy. In this case, just initialize the parameter with `ls=swapfi`.|\n| 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`.|\n\nExample involving Local Search with the Swap Best Improvement, bellow:\n\n<pre><code>\n#Usage example\nfrom pfsp.metaheuristics import multistart\n\nbest_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)\n\n</code></pre>\n\nExample involving Local Search with the Swap First Improvement, bellow:\n\n<pre><code>\n#Usage example\nfrom pfsp.metaheuristics import multistart\n\nbest_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)\n\n\n</code></pre>\n### GRASP\nThe function implements the GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic (FEO and Resende, 1995) using a constructive approach based on the Restricted Candidate List, as detailed in Resende and Ribeiro (2019). This library approach includes a constructive phase followed by a local search that utilizes the swap operator, applying either the best improvement strategy or the first improvement strategy. Ultimately, the function returns the best sequence found, the best associated makespan, the number of iterations executed, the execution time, and the matrix of completion times for each task on each machine.\n\nParameter | Description |\n|------------|-------|\n| number_jobs | Number of jobs |\n| number_machines | Number of machines |\n| processing_times_array | Matrix with processing times for each job of each machine|\n| alpha | between 0 and 1|\n| max_iterations | Integer number of iterations executed |\n| ls | Local search strategy, with two options: `ls=swapbi`, which performs local search with the swap neighborhood operator using the best improvement strategy. It is also possible to perform local search with the swap using the first improvement strategy. In this case, just initialize the parameter with `ls=swapfi`.|\n| 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`.|\n\nExample involving Local Search with the Swap Best Improvement, bellow:\n\n\n<pre><code>\n#Usage example\nfrom pfsp.metaheuristics import grasp\n\nbest_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)\n\n</code></pre>\n\nExample involving Local Search with the Swap First Improvement, bellow:\n<pre><code>\n#Usage example\nfrom pfsp.metaheuristics import grasp\n\nbest_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)\n</code></pre>\n\n## References\n- 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\u2013284, 2012.\n- 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\u201395, 1983. ISSN 0305-0483. Access: https://www.sciencedirect.com/science/article/pii/0305048383900889.\n- TAILLARD, Scheduling instances: benchmarks for basic scheduling problems. 1993. 30 set. 2024. Access: http://mistic.heig-vd.ch/taillard/problemes.dirordonnancement.dir/ordonnancement.html.\n- 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\n- FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, n. 2, p. 109\u2013133, 1995.\n- RESENDE, Maur\u00edcio 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\u2013220.\n",
"bugtrack_url": null,
"license": null,
"summary": "Package to facilitate studies about Permutation Flow Shop Scheduling Problem (PFSP)",
"version": "1.0.2",
"project_urls": null,
"split_keywords": [
"permutation",
"flowshop"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "f5b3befa21efafb46d45820cefc45bf0ff098e02ae4a07153dee39f35f68b7b0",
"md5": "5482c680101ed5601086913ad9a5c337",
"sha256": "05955586cba7aa13996e8be43db61045db36a959af35205f7b1d4383f863b0ff"
},
"downloads": -1,
"filename": "permutation_flowshop-1.0.2.tar.gz",
"has_sig": false,
"md5_digest": "5482c680101ed5601086913ad9a5c337",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 10640,
"upload_time": "2024-10-21T19:13:39",
"upload_time_iso_8601": "2024-10-21T19:13:39.527567Z",
"url": "https://files.pythonhosted.org/packages/f5/b3/befa21efafb46d45820cefc45bf0ff098e02ae4a07153dee39f35f68b7b0/permutation_flowshop-1.0.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-10-21 19:13:39",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "permutation-flowshop"
}
