AA Flashcards Scheduling Problems

Q 4inlr
Wie lautet die three field notation für scheduling problems?
? 7hli

Q 6t75j
Wie lautet die Formel für makespan?
? 7ams

Q 3k1ik
Wie lautet die Formel für sum of completion times?
? 5agm

Q 251t3
Was ist der beste Weg für $1||\sum w_j{C}_j$?
? z355
Smith’s Rule:
oder by $\frac{w_j}{p_j}$

Q 1gh8s

? 1nib
model as Minimum-cost bipartite matching

1. Add dummy jobs with cost 0 to have $n\cdot m$ jobs. ($n\cdot m-n$ jobs)
2. Every machine has $n$ jobs.
3. Connect every Job $j$ to slot $k$ of machine $i$ with cost $k\cdot p_{ij}$
4. Run the jobs in the slots per machine in reveres order.
   

Q 5gejs

? 722n

$$q=\max \left(\frac{1}{m}\sum _{j=1}^m{p}_j,\underset{j\in [n]}{\max }(p_j)\right)$$

Q 61hc2

? 134n
model as Max Flow Problem

then use binary search to find $T$