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 [email protected]

    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
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.