2
$\begingroup$

I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found one processor, or n processors - but none for two. I thought it'd be popular but I can't find if anyone's done this before?

My idea is just like the normal interval scheduling algorithm, to implement a greedy approach. First, sort by earliest starting time. Then, start by scheduling the first job to the first processor. The second job to the second processor. From there, schedule the next job to the processor who is going to finish their job first.

I think it would work, but I think this is in O(n^2) time and I'm trying to get to O(n) or O(n log n)

Any help is appreciated :)

$\endgroup$

1 Answer 1

3
$\begingroup$

The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion when you looked for algorithms.

Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/query/ -- You select the properties of your problem and will receive an overview of known results. Your case is called $P2 \mid r_j \mid C_\mathit{max}$ on that page. This is not quite your setting, as this assumes that the finishing times are the same for all tasks. But even in this slightly easier case, the web page gives you a reference for an NP-completeness proof for your problem:

Complexity of machine scheduling problems, Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P., Ann. of Discrete Math., Vol. 1, p.343-362 1977.

So your algorithm will probably not yield a feasible schedule whenever there exists one.

$\endgroup$
1
  • $\begingroup$ Also look at Pinedo's scheduling textbook. $\endgroup$ Jan 28, 2020 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.