Scheduling with batch objectives

This dissertation considers batch scheduling problems where sets of jobs are grouped into batches. The composition of a batch is prespecified and the objective function is associated with the completion time of the batches. While a machine can process only one job at a time, multiple machines can process simultaneously jobs in a batch. We allow for restrictions on the number of jobs in the shop at the same time. Except for some specialized single machine cases, analysis of these types of problems has not appeared in the literature. While the structure is simple, the problem has various real world applications such as scheduling customer orders, scheduling the production of components for subsequent assembly into final products, crane scheduling at a port, and automotive repair shop scheduling.; First, we examine batch scheduling problems with no restrictions on the number of jobs simultaneously in the machine shop. We show that the problem of minimizing the sum of batch completion times on two parallel identical machines is binary NP-complete. We present four simple heuristics which use simple scheduling rules such as smallest batch first, list scheduling, and longest processing time first. We determine the worst case bounds on the relative error and show that that the bounds are tight. Also, we extend the first two heuristics to solve the problems with an arbitrary number of parallel identical machines. We show that the worst case bounds are m and 2 {dollar}-{dollar} 1/m, respectively. Finally, we empirically evaluate heuristics H3 and H4.; We study two variations of the problem of minimizing the sum of batch completion times on two parallel identical machines. The first variation is the case where the batch sequence is fixed. We show that this problem is binary NP-complete. This situation arises in practice when a manufacturer employs a policy to determine processing order of batches. Two such policies are first come first served and priority batch scheduling. We develop an optimal dynamic programming (DP) algorithm which runs in pseudo-polynomial time.; Another variation that we examine is when the job-machine assignment is fixed. This type of problem occurs frequently in industrial settings when different machines perform different tasks. For example, consider a manufacturing facility which produces personal computers. In the facility, a monitor and a keyboard are produced separately on different machines, but they are shipped together as one final product. We show that this problem is unary NP-complete, and we develop an optimal DP algorithm.; Next, we establish that the problem of minimizing the sum of batch completion times on an arbitrary number of parallel identical machines is unary NP-complete. We develop optimal solution procedures for some problems with unit processing times.; We also examine problems where there are restrictions on the number of jobs simultaneously in the machine shop. We show that under this restriction, both minimizing the makespan and minimizing the sum of batch completion times on an arbitrary number of parallel identical machines are unary NP-complete. Also, we develop optimal solution procedures for some problems with unit processing times.