摘要
考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序问题.每个工件具有各自的安装时间和加工时间(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.
出处
《郑州大学学报(理学版)》
CAS
北大核心
2011年第2期1-3,9,共4页
Journal of Zhengzhou University:Natural Science Edition
基金
河南省基础与前沿技术研究计划资助项目
编号082300410070
河南工业大学校级科研基金项目
编号09XJC008
10XZR010
关键词
单机排序
在线
继列分批
不相容的工件组
竞争比
single-machine scheduling
on-line
serial-batching
incompatible job families
worstcase ratio