Published January 1, 2019
| Version v1
Publication
Open
Evaluating the performance of constructive heuristics for the blocking flow shop scheduling problem with setup times
- 1. Universidade Tecnológica Federal do Paraná
- 2. Universidade de São Paulo
Description
This paper addresses the minimization of makespan for the permutation flow shop scheduling problem with blocking and sequence and machine dependent setup times, a problem not yet studied in previous studies.The 14 best known heuristics for the permutation flow shop problem with blocking and no setup times are pre-sented and then adapted to the problem in two different ways; resulting in 28 differ-ent heuristics.The heuristics are then compared using the Taillard database.As there is no other work that addresses the problem with blocking and sequence and ma-chine dependent setup times, a database for the setup times was created.The setup time value was uniformly distributed between 1% and 10%, 50%, 100% and 125% of the processing time value.Computational tests are then presented for each of the 28 heuristics, comparing the mean relative deviation of the makespan, the computa-tional time and the percentage of successes of each method.Results show that the heuristics were capable of providing interesting results.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تتناول هذه الورقة التقليل إلى أدنى حد من مشكلة جدولة متجر تدفق التقليب مع الحجب والتسلسل وأوقات الإعداد المعتمدة على الماكينة، وهي مشكلة لم تتم دراستها بعد في الدراسات السابقة. تم إنشاء 14 استدلالًا معروفًا لمشكلة متجر تدفق التقليب مع الحجب ولا يتم إرسال أوقات الإعداد مسبقًا ثم يتم تكييفها مع المشكلة بطريقتين مختلفتين ؛ مما يؤدي إلى 28 استدلالًا مختلفًا. ثم تتم مقارنة الاستدلال باستخدام قاعدة بيانات تيلارد. نظرًا لعدم وجود عمل آخر يعالج مشكلة الحجب والتسلسل وأوقات الإعداد المعتمدة على الماكينة، تم إنشاء قاعدة بيانات لأوقات الإعداد. تم توزيع قيمة وقت الإعداد بشكل موحد بين 1 ٪ و 10 ٪ و 50 ٪ و 100 ٪ و 125 ٪ من قيمة وقت المعالجة. ثم يتم تقديم الاختبارات الحسابية لكل من 28 استدلالًا، ومقارنة الانحراف النسبي المتوسط للماكسبان، والوقت الحسابي ونسبة النجاحات لكل طريقة. تظهر النتائج أنه كان قادرًا على تقديم نتائج مثيرة للاهتمام.Translated Description (French)
Cet article aborde la minimisation du makepan pour le problème de planification de l'atelier de flux de permutation avec le blocage et les temps de configuration dépendants de la séquence et de la machine, un problème qui n'a pas encore été étudié dans les études précédentes. Les 14 heuristiques les plus connues pour le problème de l'atelier de flux de permutation avec le blocage et aucun temps de configuration sont préétablies puis adaptées au problème de deux manières différentes ; résultant en 28 heuristiques différentes. Les heuristiques sont ensuite comparées à l'aide de la base de données Taillard. Comme il n'existe aucun autre travail qui aborde le problème du blocage et des temps de configuration dépendants de la séquence et de la machine, une base de données pour les temps de configuration a été créée. La valeur du temps de configuration a été uniformément répartie entre 1 % et 10 %, 50 %, 100 % et 125 % de la valeur du temps de traitement. Des tests informatiques sont ensuite présentés pour chacune des 28 heuristiques, comparant l'écart relatif moyen du makepan, le temps de calcul et le pourcentage de succès de chaque méthode. Les résultats montrent que les heuristiques étaient capables de fournir des résultats intéressants.Translated Description (Spanish)
Este documento aborda la minimización de makepan para el problema de programación del taller de flujo de permutación con bloqueo y secuencia y tiempos de configuración dependientes de la máquina, un problema aún no estudiado en estudios anteriores. Las 14 heurísticas más conocidas para el problema del taller de flujo de permutación con bloqueo y sin tiempos de configuración se presentan previamente y luego se adaptan al problema de dos maneras diferentes; resultando en 28 heurísticas diferentes. Las heurísticas se comparan utilizando la base de datos Taillard. Como no hay otro trabajo que aborde el problema con el bloqueo y la secuencia y los tiempos de configuración dependientes de ma-chine, se creó una base de datos para los tiempos de configuración. El valor del tiempo de configuración se distribuyó uniformemente entre el 1% y el 10%, el 50%, el 100% y el 125% del valor del tiempo de procesamiento. Las pruebas computacionales se presentan para cada una de las 28 heurísticas, comparando la desviación relativa media del makepan, el tiempo computacional y el porcentaje de éxitos de cada método. Los resultados muestran que las heurísticas fueron capaces de proporcionar resultados interesantes.Files
j.ijiec.2018.5.002.pdf
Files
(1.3 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:75ebeceb0b681c1741446d918db6a0f4
|
1.3 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- تقييم أداء الاستدلالات البناءة لمشكلة جدولة متجر تدفق الحجب مع أوقات الإعداد
- Translated title (French)
- Évaluer la performance des heuristiques constructives pour le problème de planification de l'atelier de flux bloquant avec les temps de configuration
- Translated title (Spanish)
- Evaluar el rendimiento de la heurística constructiva para el problema de programación del taller de flujo de bloqueo con los tiempos de configuración
Identifiers
- Other
- https://openalex.org/W2811225675
- DOI
- 10.5267/j.ijiec.2018.5.002
References
- https://openalex.org/W2811225675