考虑订单类型的两台平行批处理机在线调度模型研究

Online Two Parallel Batch Machines Scheduling with Order Types

探讨了两台平行批处理机的调度决策问题,着重考虑了订单具有不同加工类型、同一批次只能加工相同类型的订单以及机器批容量有限的调度情形。针对订单实时到达且需要立即决策是否接受的实际情景,运用在线理论构建了平行机批调度在线模型。证明了该问题的竞争比下界为2Bw/(1+√Bw),其中B和w分别表示批容量和单个订单的最大完工收益。进而设计给出了收益阈值算法PT并证明其对于订单具有紧交货期限的情形竞争比为2(1+Bw)(1+√Bw);对于非紧交货期限的情形,证明了修正的PT算法具有竞争比为1+2(1+Bw)(1+√Bw)。

The problem of order processing on two parallel batch machines where orders are of different types is investigated in this paper.Each order type corresponds to a uniform processing time,order size and revenue of order.The machines are of bounded capacities,and each processing batch consists of orders with identical type.The problem originates from catering service industry and other manufacturing applications in internet economy era,where processing orders collected from different customers over internet channel can be handled jointly and simultaneously.This processing mode can improve the utilization efficiency of the corresponding manufacturing or service resources,and make customer demand be better satisfied.The online scenario is considered where orders arrive over time,and the full information of each order can only be released to the decision-maker on its arrival.The decision-maker has to decide immediately whether to accept the order on its arrival and make a feasible processing schedule for accepted orders as well.An online scheduling model is established,where the objective of the model is to maximize the total revenue of completed order.For solving online problems,the general idea is to design online algorithms,and the parameter of competitive ratio is usually adopted to measure their performances.A lower bound of competitive ratio is first proven for the considered problem such that any online algorithms cannot be better than2Bw/(1+√Bw)-competitive,where B and w are the batch capacity and maximum revenue of one order,respectively.Then both cases with tight and non-tight deadlines of orders are investigated for the problem under consideration,constructing online algorithms and using the method of worst-case analysis to prove their competitive ratios theoretically.For the case with tight deadline,an online algorithm named Profit Threshold is proposed and its competitive ratio of2(1+Bw)(1+√Bw)is proven.For the case with non-tight deadline,a revised Profit Threshold algorithm is presented and it is proved1+2(1+Bw)(1+√Bw)-competitive.Finally it is shown that for both cases,the gaps between upper bounds and lower bounds of competitive ratio are small,especially when the values of batch capacity and maximum revenue of one order are relatively large.