GRASP to minimize total weighted tardiness in a permutation flow shop environment

Lina Paola Molina-Sánchez, Eliana María González-Neira

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)161-176
Number of pages16
JournalInternational Journal of Industrial Engineering Computations
Volume7
Issue number1
DOIs
StatePublished - 01 Dec 2016

Keywords

  • Apparent tardiness cost (ATC)
  • GRASP
  • Permutation flow shop (PFS)
  • Total weighted tardiness (TWT)
  • Weighted earliest due date (WEDD)
  • Weighted modified due date (WMDD)

Fingerprint

Dive into the research topics of 'GRASP to minimize total weighted tardiness in a permutation flow shop environment'. Together they form a unique fingerprint.

Cite this