GRASP to minimize total weighted tardiness in a permutation flow shop environment
This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to mi...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Growing Science
2016-01-01
|
Series: | International Journal of Industrial Engineering Computations |
Subjects: | |
Online Access: | http://www.growingscience.com/ijiec/Vol7/IJIEC_2015_23.pdf |
_version_ | 1798046141573496832 |
---|---|
author | Lina Paola Molina-Sánchez Eliana María González-Neira |
author_facet | Lina Paola Molina-Sánchez Eliana María González-Neira |
author_sort | Lina Paola Molina-Sánchez |
collection | DOAJ |
description | This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to minimize the total weighted tardiness, since it is an important sequencing criterion not only for on time delivery jobs but also for customer satisfaction. To solve the problem, GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is proposed as a solution, which has shown competitive results compared with other combinatorial problems. In addition, two utility functions called Weighted Modified Due Date (WMDD) and Apparent Tardiness Cost (ATC) are proposed to develop GRASP. These are based on dynamic dispatching rules and also known for solving the problem of total weighted tardiness for single machine scheduling problem. Next, an experimental design was carried out for comparing the GRASP performance with both utility functions and against the WEDD dispatching rule results. The results indicate that GRASP-WMDD could improve the total weighted tardiness in 47.8% compared with WEDD results. Finally, the GRASP-WMDD performance for the PFS total tardiness problem was evaluated, obtaining a relative deviation index of 13.89% and ranking the method over 26 heuristics and metaheuristics. |
first_indexed | 2024-04-11T23:32:42Z |
format | Article |
id | doaj.art-aea1f19949de4d51aed5093519fe774f |
institution | Directory Open Access Journal |
issn | 1923-2926 1923-2934 |
language | English |
last_indexed | 2024-04-11T23:32:42Z |
publishDate | 2016-01-01 |
publisher | Growing Science |
record_format | Article |
series | International Journal of Industrial Engineering Computations |
spelling | doaj.art-aea1f19949de4d51aed5093519fe774f2022-12-22T03:57:05ZengGrowing ScienceInternational Journal of Industrial Engineering Computations1923-29261923-29342016-01-017116117610.5267/j.ijiec.2015.6.004GRASP to minimize total weighted tardiness in a permutation flow shop environmentLina Paola Molina-SánchezEliana María González-Neira This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to minimize the total weighted tardiness, since it is an important sequencing criterion not only for on time delivery jobs but also for customer satisfaction. To solve the problem, GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is proposed as a solution, which has shown competitive results compared with other combinatorial problems. In addition, two utility functions called Weighted Modified Due Date (WMDD) and Apparent Tardiness Cost (ATC) are proposed to develop GRASP. These are based on dynamic dispatching rules and also known for solving the problem of total weighted tardiness for single machine scheduling problem. Next, an experimental design was carried out for comparing the GRASP performance with both utility functions and against the WEDD dispatching rule results. The results indicate that GRASP-WMDD could improve the total weighted tardiness in 47.8% compared with WEDD results. Finally, the GRASP-WMDD performance for the PFS total tardiness problem was evaluated, obtaining a relative deviation index of 13.89% and ranking the method over 26 heuristics and metaheuristics.http://www.growingscience.com/ijiec/Vol7/IJIEC_2015_23.pdfPermutation Flow Shop (PFS)Total Weighted Tardiness (TWT)GRASPWeighted Modified Due Date (WMDD)Apparent Tardiness Cost (ATC)Weighted Earliest Due Date (WEDD) |
spellingShingle | Lina Paola Molina-Sánchez Eliana María González-Neira GRASP to minimize total weighted tardiness in a permutation flow shop environment International Journal of Industrial Engineering Computations Permutation Flow Shop (PFS) Total Weighted Tardiness (TWT) GRASP Weighted Modified Due Date (WMDD) Apparent Tardiness Cost (ATC) Weighted Earliest Due Date (WEDD) |
title | GRASP to minimize total weighted tardiness in a permutation flow shop environment |
title_full | GRASP to minimize total weighted tardiness in a permutation flow shop environment |
title_fullStr | GRASP to minimize total weighted tardiness in a permutation flow shop environment |
title_full_unstemmed | GRASP to minimize total weighted tardiness in a permutation flow shop environment |
title_short | GRASP to minimize total weighted tardiness in a permutation flow shop environment |
title_sort | grasp to minimize total weighted tardiness in a permutation flow shop environment |
topic | Permutation Flow Shop (PFS) Total Weighted Tardiness (TWT) GRASP Weighted Modified Due Date (WMDD) Apparent Tardiness Cost (ATC) Weighted Earliest Due Date (WEDD) |
url | http://www.growingscience.com/ijiec/Vol7/IJIEC_2015_23.pdf |
work_keys_str_mv | AT linapaolamolinasanchez grasptominimizetotalweightedtardinessinapermutationflowshopenvironment AT elianamariagonzalezneira grasptominimizetotalweightedtardinessinapermutationflowshopenvironment |