Title
A Tabu Search Approach For Proportionate Multiprocessor Open Shop Scheduling
Keywords
Makespan; Multiprocessor open shop; Scheduling; Tabu search
Abstract
In the multiprocessor open shop scheduling problem, jobs are to be processed on a set of processing centers - each having one or more parallel identical machines, while jobs do not have a pre-specified obligatory route. A special case is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the processing time on a given center is not job-dependent. Applications of the PMOSP are evident in health care systems, maintenance and repair shops, and quality auditing and final inspection operations in industry. In this paper, a tabu search (TS) approach is presented for solving the PMOSP with the objective of minimizing the makespan. The TS approach utilizes a neighborhood search function that is defined over a network representation of feasible solutions. A set of 100 benchmark problems from the literature is used to evaluate the performance of the developed approach. Experimentations show that the developed approach outperforms a previously developed genetic algorithm as it produces solutions with an average of less than 5 % deviation from a lower bound, and 40 % of its solutions are provably optimal. © 2013 Springer Science+Business Media New York.
Publication Date
1-1-2014
Publication Title
Computational Optimization and Applications
Volume
58
Issue
1
Number of Pages
187-203
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1007/s10589-013-9621-0
Copyright Status
Unknown
Socpus ID
84898862611 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/84898862611
STARS Citation
Abdelmaguid, Tamer F.; Shalaby, Mohamed A.; and Awwad, Mohamed A., "A Tabu Search Approach For Proportionate Multiprocessor Open Shop Scheduling" (2014). Scopus Export 2010-2014. 9697.
https://stars.library.ucf.edu/scopus2010/9697