Job shop scheduling with unit length tasks (Q2905324)

In the job shop scheduling problem a set of jobs, each consisting of a group of tasks, needs to be scheduled on a group of machines to minimize the maximum completion time, or makespan. Each task requires the use of a particular machine for a predetermined amount of time. The paper considers the online version of the problem with 2 jobs and tasks of unit length. In the online version of the job shop scheduling problem, the tasks of a job are not specified at the beginning, but disclosed to the algorithm one at a time. For each task the online algorithm must make an irrevocable decision as to where the task is to be scheduled.NEWLINENEWLINEThe paper presents a very simple deterministic algorithm with asymptotic competitive ratio 1 for the case when one of the jobs has at least twice as many tasks as the other one. The authors also give a simple randomized online algorithm with expected asymptotic competitive ratio 1 for the case when the above condition on the number of tasks of the jobs is not satisfied. Finally, a randomized online algorithm with expected asymptotic competitive ratio 1 is also presented for the case of 3 jobs, each having the same number of tasks.