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" [...]


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.