Scheduling with Agreeable Release Times and Due Dates on a Single Continuous Batch Processing Machine
释放时间和工期同序的单机连续型批调度问题

We consider the problem of continuous batch scheduling arisen from the heating-process of blooms in the steel industry,where each job has release time and a due date,each heating furnace is modeled as continuous batch processing machine and the jobs in the same batch enter and leave the machine in periods.In this paper,the jobs release time and due dates are assumed to be agreeable.We consider two different objective functions:minimize the maximum tardiness and minimize the number of tardy jobs.We study the complexity of the problems and prove that both of them are NP-hard in the strong sense.We also provide optimal algorithms with polynomial running times for the case where the jobs release time,due dates,and processing time are agreeable,respectively.