Online Scheduling on a Bounded Batch Machine with Same-Length-Job Families

We investigate an online scheduling problem on a bounded batch machine with [Formula: see text] incompatible job families, in which the jobs are released over time and the jobs belonging to the same family have the same processing times. The goal is to minimize the maximum completion time. A machine can process at most [Formula: see text] jobs simultaneously as a batch, where [Formula: see text] is finite. A batch only contains the jobs from the same family. KRT setting means that no job is released when the machine is busy. In this paper, we consider the above model under two environments: (1) KRT setting and (2) general setting. In the KRT setting, we provide the lower bounds [Formula: see text] for [Formula: see text] and [Formula: see text] for [Formula: see text]. In the general setting, we provide the lower bounds [Formula: see text] for [Formula: see text] and [Formula: see text] for [Formula: see text]. We further present an online algorithm, which is the best possible when [Formula: see text] for the KRT setting and when [Formula: see text] for the general setting.