Batch scheduling on uniform machines to minimize total flow-time

摘要

The solution of the classical batch scheduling problem with identical jobs and setup times to minimize flowtime is known for twenty five years. In this paper we extend this result to a setting of two uniform machines with machine-dependent setup times. We introduce an O(n) solution for the relaxed version (allowing non-integer batch sizes), followed by a simple rounding procedure to obtain integer batch sizes.