最小化时间表长的带有多个工件组单机无界继列批在线排序

摘要

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序间题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.%The unbounded single-machine serial-batching scheduling problem with family jobs was considered under on-line setting. The setup time and processing time of each job were denoted by (s,p). And the jobs with different families were not allowed to be processed on the same batch.The objective was to minimize the maximum completion time of the jobs (i. e. makespan). A best possible on-line algorithm H∞ with a worst-case ratio of 2 was provided.