A tabu search approach for proportionate multiprocessor open shop scheduling

    Authors

    T. F. Abdelmaguid; M. A. Shalaby;M. A. Awwad

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Comput. Optim. Appl.

    Keywords

    Scheduling; Multiprocessor open shop; Tabu search; Makespan; TIME APPROXIMATION SCHEME; GENETIC ALGORITHM; OPTIMIZATION; Operations Research & Management Science; Mathematics, Applied

    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.

    Journal Title

    Computational Optimization and Applications

    Volume

    58

    Issue/Number

    1

    Publication Date

    1-1-2014

    Document Type

    Article

    Language

    English

    First Page

    187

    Last Page

    203

    WOS Identifier

    WOS:000334524000007

    ISSN

    0926-6003

    Share

    COinS