The Use Of Branch-and-Bound Method In Scheduling Problem On Parallel Machines

Scheduling is an important research field. Batch machine scheduling problem has its root in various application areas and attracted a lot of attention recently. In the paper we consider the problem of scheduling jobs with intree precedence constraints on two and more than two indentical parallel machines to minimize makespan. Three chapters are included in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we consider the problem P2\intree; rj\Cmax that has been considered an open problem before. We introduce for the first time the notion of level-by-level structure into scheduling which has been a concept in the theory of strategy. We use the level-by-level structure to reflect the precedence constraints among the jobs, on the base of which we set forth a branch-and-bound algorithm to give the optimal schedule for problem P2|intree;rj|Cmax.Clearly only when it has arrived and all its predecessors have been completed can a job be started. We establish a label for each job; The label consists of 2 parts: The second represents the earliest starting time of the job if it doesn't break the precedence constraints. The first part marks the level the job belonging to,regulating that if job Jj is successor of job Jj, then lj = li +1. If there are precedence constraints between job Jj and job Jj, lj can't be equal to lj. After we devide the jobs into different levels according to their l label, the job in the second level must have predecessor in the firstlevel, and so is any job in higher levels. Because the precedence constraints are in intree type, the last level must contain only one job(assuming it to be Jn), also r'n is the largest. We use r'n + pn as a lower bound for the objective function Cmax.The jobs that are started earliest can only be chosen from the first level, so we choose two jobs arbitrarily and process them on two machines, thus producing root nodes. Each root node has a lower bound, which is the ealiest starting time of the last job. Having chosen a root node that has the smallest lower bound, we choose two jobs arbitrarily from the lowest level of the root node selected and process them on two machines, thus producing branch nodes, each has a lower bound also. If we have found such a node, which contains all jobs, moreover, the actual starting time of the last job is no more than the lower bound of all other nodes, then stop; We have found the optimal schedule.In the third chapter, we study the problem Pm|intree;pj = 1; rj\Cmax that has not been considered before. Using the branch-and-bound algorithm we give the optimal schedule for the problem. For all jobs are unit jobs, and their release dates are integers, the branch-and-bound method can be simplyfied. When deviding all jobs into different levels and establishing root nodes, we need only consider the jobs with the smallest release date in the first level. We do the same job when establishing every branch node in every step. Using the branch-and-bound method, we can find the optimal schedule for problem...