Packet Routing and Scheduling

Among the most important problems in combinatorial optimization are scheduling problems. In this paper, machine scheduling is considered. Usually in such problems a set of jobs and a set of machines are given. The task is to assign the jobs to the machines and to determine a schedule for each machine. The schedule determines at what times the machine will process the jobs assigned to it. Often, constraints must be taken into account. Typical constraints are times by which certain jobs must be completed (deadlines), that some jobs can only be processed when certain other jobs are completed (precedence constraints), or that some jobs are only available from a given time (release dates).