0
$\begingroup$

I have been thinking about the following problem:

Let $J$ be a set of jobs that need to be performed. Each jobs comprises of some number ($>1$) of tasks, and a job is considered finished when all of the tasks have been completed. Find an ordering to perform the tasks such that the sum of the maximum time needed to finish each job is minimised. Assume that the time needed to finish each task is unary and that the time to finish each job is the time that passes from when one of the tasks of the job starts until the last task of the job finishes.

For example:

Suppose we have 3 jobs: $J_1 = \{a,b,c\}$, $J_2 = \{b,d\}$ and $J_3 = \{a,c\}$, where $a,b,c,d$ are tasks. An optimal ordering for this set of tasks is $a-c-b-d$ because the time needed to finish $J_1$ is 2, the time needed to finish $J_2$ is 1 and the time needed to finish $J_3$ is also 1. In total, the maximum time $t$ to finish all jobs is 2+1+1 = 4.

An example of a bad ordering is $b-a-c-d$ would result in $t = 2+3+1 = 6$

I was thinking that maybe I could use dynamic programming to find an optimal ordering but ultimately I cannot do any better than ending up checking every possible order. Is there any trick to finding optimal orders or are there any related problems I could study?

$\endgroup$
4
  • 1
    $\begingroup$ Does this answer your question? Finding optimal sequence of questions to minimize total student time $\endgroup$
    – xskxzr
    Jan 10 '20 at 18:30
  • $\begingroup$ @xskxzr It refers to the same problem, but the linked question addresses the question of whether the problem is NP-complete or not, while I was wondering if there is some general methodology for solving this type of problems without enumerating all possible orderings (but not necessarily in polynomial time) or if this type of problems has been studied in general. $\endgroup$
    – phan801
    Jan 10 '20 at 20:04
  • $\begingroup$ It looks like this is a problem different from the linked question, Finding optimal sequence of questions to minimize total student time. The time for a job here starts when one of the tasks of the job starts while all students enter the tutorial session in the beginning in the linked question. This distinction seems significant. $\endgroup$
    – John L.
    Jan 15 '20 at 20:35
  • $\begingroup$ @JohnL.You are right, I missed that detail on the linked question. $\endgroup$
    – phan801
    Jan 15 '20 at 20:52

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.