Scheduling jobs with two people where part (a) of each job must be finished before part (b)

Question

• There are n jobs each consisting of two parts: a and b.
• There are two people:
  • person A is completing part a of each job (one at a time), and
  • person B is completing part b of each job (also one at a time).
• Constraint: part a of each job must be completed before part b
• We are given for each i:
  • a[i] : the time that it takes to complete part a of job i; and,
  • similarly, b[i] for part b of job i.

The problem is to find an algorithm to determine

• an order such that the total time to complete all jobs is minimized.

Note: A and B are able to work in parallel.

My question is: how can we solve this problem? And, what is a good reference to learn to solve similar scheduling problems?

Answer 1

What you are looking for is Johnson's algorithm for job scheduling.

Johnson's algorithm works as follows on the situation described in the question.

1. Select a part of a job with the shortest completion time (break ties arbitrarily).

   Suppose the job is job $i$.

   • If the part is $a[i]$, schedule job $i$ first.
   • If the part is $b[i]$, schedule job $i$ last.

   Eliminate job $i$ from further consideration.

2. Repeat step 1, working towards the center of the job schedule until all jobs have been scheduled.

---

When implementing the algorithm above, we can first sort all jobs by the shorter completion time of part (a) or part (b) of each job.

The time-complexity of the algorithm is $O(n\log n)$.

---

There are huge numbers of problems and algorithms in job scheduling such as job-shop scheduling, flow-shop scheduling and open-shop scheduling. You might be interested in some articles/ that returned by google search for "job scheduling algorithms".

If you are programming for fun or for programming contest, you could learn scheduling algorithms on a case-by-case approach. If you are writing for production software, you may want to read the chapters on scheduling of some books on operating systems. Just my two cents. Depending on your need, there are a variety of choices to learn.