Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time |
| |
| Authors: | TC Edwin Cheng Qingqin Nong Chi To Ng |
| |
| Institution: | 1. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;2. Department of Information and Computation Science, College of Mathematical Sciences, Ocean University of China, Qingdao, Shandong 266100, People's Republic of China |
| |
| Abstract: | In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 |
| |
| Keywords: | scheduling concurrent open shop approximation scheme |
|
|
