Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
computer science
An approximate decomposition algorithm for scheduling on parallel machines with heads and tails
Computers and Operations Research, Volume 34, No. 3, Year 2007
Notification
URL copied to clipboard!
Description
We address the makespan minimization for parallel identical machines subject to heads and tails. This problem is NP-hard in the strong sense. We show that the worst-case performance of Jackson's algorithm is improved by using a preprocessing algorithm, and we propose an approximate decomposition algorithm which requires iteratively solving a sequence of two-machine problems. We present the results of an extensive computational study on large instances with up to 2000 jobs and 100 machines which show that the proposed heuristic is fast and yields in most cases schedules with relative deviation from a lower bound less than 0.2%. © 2005 Elsevier Ltd. All rights reserved.
Authors & Co-Authors
Gharbi, Anis
Tunisia, La Marsa
University of Carthage, Ecole Polytechnique de Tunisie
Tunisia, Ariana
Institut Supérieur D'informatique
Haouari, Mohamed
Tunisia, La Marsa
University of Carthage, Ecole Polytechnique de Tunisie
Statistics
Citations: 28
Authors: 2
Affiliations: 2
Identifiers
Doi:
10.1016/j.cor.2005.05.012
ISSN:
03050548