有服务等级约束的有界分批列表在线排序算法  

An algorithm for online-list scheduling with bounded batch under a grade of service provision

作　　者：呼雨婷 柴幸 HU Yuting;CHAI Xing(College of Science,Henan University of Technology,Zhengzhou 450001,China)

机构地区：[1]河南工业大学理学院,河南郑州450001

出　　处：《商丘师范学院学报》2025年第3期1-5,共5页Journal of Shangqiu Normal University

基　　金：国家自然科学基金项目(12001169)。

摘　　要：探讨两台机器上有服务等级约束下,等长工件的有界分批列表在线排序问题.根据工件和机器的特性,有相应的等级约束,工件只能在服务等级不高于自身等级的机器上加工,目标是最小化时间表.工件可以平行批处理,在不超过批容量的前提下,多个工件可在同一批中占用同一台机器同时加工.讨论列表在线情形下,在线算法竞争比的下界,并设计与下界匹配的3/2-竞争的最好可能的在线算法.This paper is about the problem of scheduling equal-length jobs on two batching machines with a grade of service provision where the jobs and the machines are both graded.A job can be processed by a machine if and only if its grade is not higher than that of the machine.The objective is to minimize the makespan.Jobs can be processed in parallel batches under the premise of not exceeding the batch capacity,and multiple jobs can be processed simultaneously in the same batch occupying the same machine.We discuss the lower bound of the competition ratio of online algorithms in the online-list case,and design the best possible online algorithm matching the lower bound of 3/2-competition.

关 键 词：服务等级约束 排序 平行机 列表在线 

分 类 号：O223[理学—运筹学与控制论]