An Ant Colony Optimization Algorithm for Scheduling Parallel Machines with Sequence-Dependent Setup Costs
Journal Title: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki - Year 2013, Vol 7, Issue 9
Abstract
The paper addresses the problem of scheduling preemptive jobs on parallel unrelated machines in the presence of renewable resource constraints and sequence-dependent setup costs. The objective is to minimize the weighted sum of makespan and setups. The problem is known to be NP-hard. To solve this problem, a heuristic is proposed which uses column generation technique and an ant colony optimization algorithm. The results of a computational experiment indicate that the heuristic is able to produce good results in reasonable computation time.
Authors and Affiliations
Ewa Figielska
Keywords
Related Articles
- EP ID EP169375
- DOI -
- Views 112
- Downloads 0
Geometric interpretation of a correlation
The study shows that the Pearson’s coefficient of correlation is equivalent to the cosine of the angle between random variables. It was found that the information about the intensity of the relationship between variables...
Identyfikacja wzorców w finansowych szeregach czasowych z wykorzystaniem hierarchicznych metod grupowania na przykładzie kursu BTC/PLN
W artykule przedstawiono zastosowanie metody Warda do identyfikacji wzorców w finansowych szeregach czasowych, na przykładzie kursu waluty kryptograficznej bitcoin. Wykorzystując zidentyfikowane wzorce, generowano progno...
Blaski i cienie synchronicznego szkolenia na odległość, na bazie doświadczeń projektu Efektywni 50+
W artykule opisano doświadczenia wyniesione z przeprowadzonych szkoleń w ramach projektu Efektywni 50+. Zrealizowano 700 godzin szkolenia, w tym 560 godzin w formie wideokonferencji. Przedstawione zostały założenia proje...
Porównanie wydajności algorytmu k-means zaimplementowanego w języku X10 i środowisku C++/MPI
W pracy opisano algorytm k-średnich oraz sposób jego implementacji w języku X10. Dokonano porównania tego rozwiązania z implementacją w języku C++11 z wykorzystaniem standardu MPI. Stwierdzono, że implementacja w języku...
Dynamics of Stochastic vs. Greedy Heuristics in Traveling Salesman Problem
We studied the relative performance of stochastic heuristics in order to establish the relations between the fundamental elements of their mechanisms. The insights on their dynamics, abstracted from the implementation de...