Scheduling Pairs of Jobs on Two Machines
Co-authorIrina N. Lushchakova
The problem of scheduling jobs on two consecutive machines to minimize the makespan is considered, provided that on each machine the jobs are grouped in pairs, i.e., batches containing exactly two jobs, not necessarily the same on each machine. The problem is related to scheduling models with batch availability and has applications to human resource management. A linear-time algorithm is presented.