Consider the following well known flow-shop problem:

We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$. Each job $J_i$ consists of a set of operations $O^i=\{O_1^i,\ldots,O_p^i\}$. Each operation $O_k^i$ requires exactly one resource $R_k^i \in R$ for a time fixed time $t_k^i$, and for each job, $J_i$ there is a set of precedence constraints (i.e., a partial order or directed graph) on the operations, $O_k^i \xrightarrow[\mathrm{before}]{} O_l^i$, stating that operation $O_k^i$ needs to finish before $O_l^i$ starts.

Is there any application of the above mentioned problem in computing (e.g. graph processing, image processing, distributed systems etc.)? Wikipedia tells me that "Flow shop scheduling may apply as well to production facilities as to computing designs" without providing a single example. I am looking for at least one example in computing in order to understand the significance of this problem in computer science. (I know the problem is NP-hard and that is enough to consider it as significant in computer science but I want to find a real world computing application which can be reduce to flow-shop problem).

  • $\begingroup$ What about car production? Each car processes the machine one at a time. Or any other production as far as there is not only one production line. Therefore it would be linear solvable for example with SIMPLEX. In computer design you can see this kind of problem when using threading for example (race conditions, deadlocks). $\endgroup$ – sascha10000 Oct 1 '16 at 17:43
  • $\begingroup$ I agree with you on manufacturing process example but can you elaborate the multi-threading example that you mentioned? In my understanding (can be be wrong), threads acquire locks in a random fashion which can not be compared to a much deterministic manufacturing process. Can you provide any reference (research publications) where they consider multithreading as a flow-shop problem? $\endgroup$ – usr109876787 Oct 1 '16 at 18:35
  • $\begingroup$ No I don't have a reference. It's just a thought. I don't had this problem in class therefore I can only try to find parallels. But I would see the CPU as a ressource (e.g. 8 cores, 4 real ones). And the Jobs are programms running and the operations maybe the instructions in the register. $\endgroup$ – sascha10000 Oct 1 '16 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.