The batch loading and scheduling problem

This paper discusses the problem of batching and scheduling of certain kind s of batch processors. Examples of these processors include heat treatment facilities, particularly in the steel and ceramics industries, as well as a variety of operations in the manufacture of integrated circuits. In genera l, for our problem there is a set of jobs waiting to be processed. Each job is associated with a given family and has a weight or delay cost and a vol ume. The scheduler must organize jobs into batches in which each batch cons ists of jobs from a single family and in which the total volume of jobs in a batch does not exceed the capacity of the processor. The scheduler must t hen sequence all the batches. The processing time for a batch depends only on the family and not on the number or the volume of jobs in the batch. The objective is to minimize the mean weighted flow time. The paper presents an integer programming formulation for this problem, gen erates a lower bound from a partial LP relaxation, provides a Polynomial al gorithm to solve a special case, and tests a set of heuristics on the gener al problem. The ability to pack jobs into batches is the key to efficient s olutions and is the basis of the different solution procedures in this pape r. The heuristics include a greedy heuristic, a successive knapsack heurist ic, and a generalized assignment heuristic. Optimal solutions are obtained by complete enumeration for small problems. The conclusions of the computational study show that the successive knapsac k and generalized assignment heuristics perform better than the greedy. The generalized assignment heuristic does slightly better than the successive knapsack heuristic in some cases, but the latter is substantially faster an d more robust. For problems with few jobs, the generalized assignment heuri stic and the knapsack heuristic almost always provide optimal solutions. Fo r problems with more jobs, we compare the heruistic solutions' values to lo wer bounds; the computational work suggests that the heuristics continue to provide solutions that are optimal or close to the optimal. The study also shows that the volume of the job relative to the capacity of the facility and the number of jobs in a family affect the performance of the heuristics , whereas the number of families does not. Finally, we give a worst-case an alysis of the greedy heuristic.