Friday, 11:00 - 11:25 h, Room: H 3004


Guangting Chen
Approximation algorithms for parallel open shop scheduling

Coauthors: Yong Chen, An Zhang


This paper investigates a new scheduling problem, namely the parallel open shop scheduling.
In this problem, each job consists of two operations, which must be non-preemptively processed by one of the m two-stage parallel open shops.
The objective is to minimize the makespan. As the problem is NP-hard, we provide the first approximation algorithm with a worst case ratio
of 2 for m machines, and for m=2, an improved algorithm with worst case ration 3/2 is further proposed. Both algorithms run in O(n log n) time.


Talk 2 of the invited session Fri.1.H 3004
"Approximation algorithms for hard problems" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.