并行设备上的差异作业批调度问题及多项式算法

Scheduling Problem of Parallel Batch-Processing Machines with Non-Identical Job Sizes and Polynomial Time Algorithm

考虑了一类作业尺寸有差异的批调度问题,加工环境为并行批处理设备。以制造跨度为优化目标,建立了基于整数规划的数学模型;分析了制造跨度最小化问题的计算复杂性,给出问题可行解规模的上下界;然后设计了一种基于LPT规则和Batch First Fit规则的近似算法,证明了算法的时间性能为O(nlogn),算法在优化制造跨度时的最坏性能比为(8/3～2/3m)。

This paper considers the problem of scheduling parallel batch-processing machines with non-identical job sizes. This kind of scheduling approach is widely applied in many industries, such as food processing industry, semi-conductor manufacturing industry, and ship scheduling at navigation docks. In this kind of scheduling, the parallel machines have the same capacity to accommodate jobs and the same velocity to process jobs. Jobs often have arbitrary sizes because they are determined by customers. Jobs are first assigned into batches when they are processed. In each batch, the total size of all the jobs cannot exceed the machine capacity. Once a batch is being processed, no interruption is allowed until all the jobs are completed. We show that the problem of minimizing makespan is NP- hard in the strong sense. In current research, single-machine problems have aroused interests. However, little research has been done on multi-machine problems. In the research of parallel-machine problems, only intelligent algorithms have been proposed but no accurate algorithms are provided. In this paper, we propose an approximation algorithm with running time of 0 （nlogn） and a performance guarantee of （8/3 -2/3m）, where n is the number of jobs and m is the number of machines. In the first part, we describe the problem and analyzeits properties. We first use an integer programming method to propose a mathematical model to understand scheduling problems. We derive the bounds on a number of feasible solutions by analyzing two special cases. The lower bound and upper bound are shown to be n! /m! and m^n , respectively. We also investigate the properties of optimal solutions. Since the problem can be converted into a bin-packing problem and all the jobs have the same processing time, we derive a lower bound of optimal solutions. In the second part, we provide apolynomial time estimation algorithm for minimizing makespan. The first step is to order jobs by their processing times. Since the processing time of a batch is determined by the longest job, we order jobs in a non-increasing order.The second step is to assign jobs into feasible batches. We use the First Fit heuristic from the head of the job list. The last step is to order batches of parallel machines. For Pm ｜｜ Cmax is also NP-hard, we order batches in a non-increasing order and put a batch on a machine whenever the machine becomes idle. The running time is shown to be O（nlogn）. By analyzing the number of batches and the mechanism of batch processing, we prove that the proposed algorithm has a performance guarantee of （8/3 -2/3m）. In summary, we provide an effective algorithmto minimize the makespan of parallel batching machines with non-identical job sizes. However, many problems remain unresolved and need further investigation. First, other objectives need to be studied such as the total weighted completion time. It is not difficult to see that the problem of minimizing total weighted completion time is NP-hard. Second, online problems are also widely encountered in practice and it is interesting to research on effective online algorithms. Third, the problems with other machine configurations like job shop are also interesting directions. Obviously, the problems are even more difficult to solve.