Scheduling an unbounded batching machine with job processing time compatibilities

The problem of scheduling nn jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in O(nlogn)O(nlogn) time and minimizing the maximum lateness is proved to be NP-hard.