关键词: 调度决策, 平行批处理机, 在线算法, 竞争比

Abstract: 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 than 2^Bw/(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 of 2(1+^Bw)/(1+√Bw) is proven. For the case with non-tight deadline, a revised Profit Threshold algorithm is presented and it is proved 1+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.

Key words: scheduling, parallel batch machines, online algorithm, competition ratio