SIMULTANEOUS RESOURCE SCHEDULING WITH BATCHING TO MINIMIZE WEIGHTED FLOW TIMES

This paper examines scheduling problems in which individual tasks requ ire several resources concurrently. We analyze the situation where, in addition to the need to schedule resources concurrently, it is possib le to choose the batch sizes of the tasks. Although such situations ar ise in both manufacturing and service firms, the likely application of these results will be to repetitive batch manufacturing situations. S everal formulations for this problem are presented. Both a lagrangian relaxation and a surrogate relaxation are developed. Heuristics based on these relaxations as well as extensive computational experiments ar e discussed. The simultaneous resource scheduling problem without batc hing is quite difficult because jobs need to be synchronized so that i ndividual jobs can capture their required simultaneous resources. Neve rtheless, if batch size is introduced as an additional variable, we sh ow that the resulting problem is in some sense easier because of the a dded flexibility provided by the ability to adjust production batch si zes, which allows us to eliminate 'gaps' in the schedule.