Loading...
Please wait, while we are loading the content...
A tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Helal, Magdy Rabadi, Ghaith Al-Salem, Ameer |
| Abstract | AbstractIn this paper we propose a tabu search implementation to solve the unrelated parallel machines scheduling problem with sequence- and machine- dependent setup times to minimize the schedule’s makespan. The problem is NP-hard and finding an optimal solution efficiently is unlikely. Therefore, heuristic techniques are more appropriate to find near-optimal solutions. The proposed tabu search algorithm uses two phases of perturbation schemes: the intra-machine perturbation, which optimizes the sequence of jobs on the machines, and the inter-machine perturbation, which balances the assignment of the jobs to the machines. We compare the proposed algorithm to an existing one that addressed the same problem. The computational results show that the proposed tabu search procedure generally outperforms the existing heuristic for small- and large-sized problems. KeywordsTabu search, Scheduling, Unrelated parallel machines, Setup times 1. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Unrelated Parallel Machine Tabu Search Algorithm Setup Time Inter-machine Perturbation Optimal Solution Tabu Search Procedure Heuristic Technique Schedule Makespan Large-sized Problem Tabu Search Implementation Machine Dependent Setup Time Intra-machine Perturbation Keywordstabu Search Computational Result Near-optimal Solution Tabu Search Perturbation Scheme |
| Content Type | Text |
| Resource Type | Article |
