AA Flashcards Scheduling Problems

q aosr/4inlr
Wie lautet die three field notation für scheduling problems?
? aosr/4inlr/m/7hli

q aosr/6t75j
Wie lautet die Formel für makespan?
? aosr/6t75j/m/7ams

q aosr/3k1ik
Wie lautet die Formel für sum of completion times?
? aosr/3k1ik/m/5agm

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

q aosr/1gh8s

? aosr/1gh8s/m/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 aosr/5gejs

? aosr/5gejs/m/722n

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

q aosr/61hc2

? aosr/61hc2/m/134n
model as Max Flow Problem

then use binary search to find $T$