Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling Pairs of Jobs on Two Machines

SpeakerVitaly Strusevich

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.