Published June 22, 2016
| Version v1
Publication
Open
<b>Evaluation of heuristics for a branch and bound algorithm to minimize the makespan in a flowshop with blocking
- 1. Universidade Tecnológica Federal do Paraná
- 2. Universidade de São Paulo
Description
This paper has the objective to evaluate the use of different methods to obtain an initial solution for the branch and bound algorithm with the objective of minimizing the makespan in a flowshop with zero buffer environment. As the problem is known to be NP-Hard, the branch and bound algorithm may take long computational time to find the best solution. The use of an initial solution may reduce the computational time, by providing an initial upper bound. In this work, the efficiency of the use of an initial solution to the Branch and Bound algorithm was evaluated by comparison of the algorithms. The branch and bound algorithm used, as well as the lower bound, was proposed by Ronconi (2005). Four heuristic methods (MM, PF, wPF, and PW) were tested using a 180 problems data. Results show that the use of an initial solution does considerably reduce the computational time.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تهدف هذه الورقة إلى تقييم استخدام طرق مختلفة للحصول على حل أولي للفرع والخوارزمية المربوطة بهدف تقليل فترة التصنيع في متجر التدفق مع بيئة عازلة صفرية. نظرًا لأن المشكلة معروفة بأنها مشكلة NP - Hard، فقد تستغرق الخوارزمية الفرعية والمحددة وقتًا حسابيًا طويلاً للعثور على أفضل حل. قد يؤدي استخدام محلول أولي إلى تقليل الوقت الحسابي، من خلال توفير حد أعلى أولي. في هذا العمل، تم تقييم كفاءة استخدام حل أولي لخوارزمية الفرع والربط من خلال مقارنة الخوارزميات. اقترح رونكوني (2005) الخوارزمية الفرعية والمقيدة المستخدمة، بالإضافة إلى الحد الأدنى. تم اختبار أربع طرق إرشادية (MM و PF و WPF و PW) باستخدام بيانات 180 مشكلة. تظهر النتائج أن استخدام الحل الأولي يقلل بشكل كبير من الوقت الحسابي.Translated Description (French)
Cet article a pour objectif d'évaluer l'utilisation de différentes méthodes pour obtenir une solution initiale pour l'algorithme de branche et lié dans le but de minimiser le makepan dans un flowhop avec un environnement tampon zéro. Comme le problème est connu pour être NP-Dur, la branche et l'algorithme lié peuvent prendre un long temps de calcul pour trouver la meilleure solution. L'utilisation d'une solution initiale peut réduire le temps de calcul, en fournissant une limite supérieure initiale. Dans ce travail, l'efficacité de l'utilisation d'une solution initiale à l'algorithme Branch and Bound a été évaluée par comparaison des algorithmes. L'algorithme de branche et de borne utilisé, ainsi que la borne inférieure, a été proposé par Ronconi (2005). Quatre méthodes heuristiques (MM, PF, wPF et PW) ont été testées à l'aide de 180 données de problèmes. Les résultats montrent que l'utilisation d'une solution initiale réduit considérablement le temps de calcul.Translated Description (Spanish)
Este trabajo tiene como objetivo evaluar el uso de diferentes métodos para obtener una solución inicial para el algoritmo de bifurcación y encuadernación con el objetivo de minimizar el makespan en un flowshop con entorno de buffer cero. Como se sabe que el problema es NP-Hard, el algoritmo de ramificación y enlace puede tardar mucho tiempo en encontrar la mejor solución. El uso de una solución inicial puede reducir el tiempo de cálculo, al proporcionar un límite superior inicial. En este trabajo, se evaluó la eficiencia del uso de una solución inicial al algoritmo Branch and Bound mediante la comparación de los algoritmos. El algoritmo de ramificación y enlace utilizado, así como el límite inferior, fue propuesto por Ronconi (2005). Se probaron cuatro métodos heurísticos (MM, PF, wPF y PW) utilizando datos de 180 problemas. Los resultados muestran que el uso de una solución inicial reduce considerablemente el tiempo de cálculo.Files
pdf.pdf
Files
(257 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:2500f71f674042230eb9a292440b0e4f
|
257 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- <b>تقييم الاستدلال لفرع وخوارزمية ملزمة لتقليل فترة التصنيع في متجر التدفق مع الحجب
- Translated title (French)
- <b>Évaluation de l'heuristique pour une branche et algorithme lié pour minimiser le makepan dans un flowhop avec blocage
- Translated title (Spanish)
- <b>Evaluación de la heurística para un algoritmo de ramificación y encuadernación para minimizar el makepan en un flowshop con bloqueo
Identifiers
- Other
- https://openalex.org/W2462005886
- DOI
- 10.4025/actascitechnol.v38i3.28438
References
- https://openalex.org/W1970586831
- https://openalex.org/W1971183889
- https://openalex.org/W1981123047
- https://openalex.org/W1985351347
- https://openalex.org/W2003685253
- https://openalex.org/W2021347904
- https://openalex.org/W2056768955
- https://openalex.org/W2066919689
- https://openalex.org/W2087409062
- https://openalex.org/W2104475423
- https://openalex.org/W2122967269
- https://openalex.org/W2131446946
- https://openalex.org/W2149085222