Batch scheduling with machine-dependent processing times on a two-machine open-shop and a two-machine job-shop
研究了两台机器开放车间和作业车间中，加工时间因机器而异的相同工件批调度问题，目标是极小化最大完工时间，并给出了多项式时间解法。
We study batch scheduling problems involving identical jobs in a two-machine open-shop and a two-machine job-shop. In contrast to most related work on batch scheduling in shop environments, we allow machine-dependent processing times. The objective is to minimise the makespan. We show that the open-shop problem can be solved in constant time. For the job-shop problem, we first consider a relaxed version in which batch sizes are allowed to be non-integer. An optimal solution to this relaxation is obtained by solving two two-machine flow-shop problems: the first considers jobs processed first on Machine 1 and then on Machine 2, while the second considers jobs processed first on Machine 2 and then on Machine 1. A rounding procedure is then applied to convert the resulting batch sizes into integers. Despite its greater complexity, we prove that the job-shop problem can still be solved in polynomial time with respect to the number of jobs. Finally, we extend our results to the case of bounded batch sizes and provide efficient solution algorithms.