科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper investigates the parallel open shop scheduling problem. In this problem each job consists of two independent operations, which must be non-preemptively processed by one of m parallel identical two-machine open shops. The objective is to minimize the makespan. Because of NP-hardness, we provide polynomial time approximation algorithms for the problem. If there are m open shops, our algorithm has a worst case ratio of 2. If only two open shops are valid, it can be improved to 3/2.
