Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM JOB SHOP SCHEDULING

• INSTANCE: Number $m\in Z^+$ of processors, set J of jobs, each $j\in J$ consisting of a sequence of $n_j$ operations $o_{i,j}$ with $1 \leq i \leq n_j$, for each such operation a processor $p_{i,j}\in[1..m]$ and a length $l_{i,j}\in N$.

• SOLUTION: A job shop schedule for J, i.e., a collection of one-processor schedules $f_p : \{o_{i,j} : p_{i,j}=p\} \rightarrow N$ such that $f_p(o_{i,j}) > f_p(o_{i',j'})$ implies $f_p(o_{i,j}) \geq f_p(o_{i',j'})+l_{i',j'}$ and such that $f_p(o_{i+1,j}) \geq f_p(o_{i,j})+l_{i,j}$.

• MEASURE: The completion time of the schedule, i.e., $\max\limits_{j\in J} f_p(o_{n_j,j})+l_{n_j,j}$.

  
  

• Good News: Approximable within $O\left( \lceil\log(\min(m\mu,l_{\mbox{\scriptsize max}}))/\log\log(m\mu)\rceil \log(m\mu)/\log\log(m\mu)\right)$, where $\mu = \max_{j \in J}n_j$ and $l_{\mbox{\scriptsize max}} = \max l_{i,j}$ [200].

• Bad News: Not approximable within 5/4$-\varepsilon$ for any $\varepsilon >0$ [466].

• Comment: Transformation from 3-PARTITION. Approximable within $O(\log^2 m)$ if each job must be processed on each machine at most once [440]. The variation in which the operations must be processed in an order consistent to a particular partial order, and the variation in which there are different types of machines, for each type, there are a specified number of identical processors, and each operation may be processed on any processor of the appropriate type, are approximable within $O(\log^2(m\mu))$ [440].

• Garey and Johnson: SS18