Premium
Polynomial time approximation algorithms for proportionate open‐shop scheduling
Author(s) -
Naderi B.,
Zandieh M.,
Yazdani M.
Publication year - 2014
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12087
Subject(s) - time complexity , scheduling (production processes) , computer science , job shop scheduling , approximation algorithm , mathematical optimization , algorithm , open shop scheduling , mathematics , flow shop scheduling , schedule , operating system
This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if n ≥ m , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, m > n , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of ( 2 − 1 / n ) that improves the bound existing for general open‐shops. Next, in the case of m > n , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where m > n .