Computational Complexity Of The Drop-line Parallel Batch Scheduling

Parallel-batching scheduling is an important modern scheduling model. The charac-teristics of parallel-batching scheduling are as follows:Multiple jobs can be assigned into a common batch to be processed simultaneously, and the processing time of a batch is given by the maximum processing time of the jobs in the batch. The maximum number of jobs contained in a batch is called the batch capacity, denoted by b. The version b=oo is called the unbounded model, and the version b<n is called the bounded model, where n is the number of jobs. In the classical parallel-batching scheduling, the people assume that the jobs contained in a common batch have the same starting time and the same completion time. That is, if a batch A has a starting time S and a processing time p, then all jobs in A have a starting time S and a completion time S+p.The parallel-batching scheduling with drop-line jobs breaks through the assumption of the classical parallel-batching scheduling, and presents new definition for the completion times of the jobs. If a batch A has a starting time S, then the starting time of each job Jj in the batch A is defined to be S, and its completion time is defined as S+Pj, where Pj is the processing time of the job Jj. By using the three-parameter notation, The parallel-batching scheduling problems with drop-line jobs can be denoted by1|p-batch, b, rj, drop-line|γ.The parallel-batching scheduling with drop-line jobs was widely used in the Container Transportation, Information Technology, and many other applied field. But, in the litera-ture, the research for the topic is in its beginning. Based on the previous work on this field, we study the computational complexity of the parallel-batching scheduling with drop-line jobs in this paper. The main results of this paper are as follows.●Problem1|p-batch, b<n, drop-line|ΣCj can be solved in O(nb(b-1) time.●Under the restriction that there are exactly K=[n/b] batches, problem1|p-batch, b<n,drop-line|ΣCj can be solved in0((nK-1)KlogK+nlogn) time.●Problem1|p-batch, b<n, drop-line, SPT|ΣCj can be solved in O(bn+n log n) time. ●Problem1|p-batch,b=∞,rj((?)),drop-line|∑fjcan be solved in O(n2P2)time, where P=maxjrj+∑jpj.●Problem1|pbatch,b=∞,rj((?)),drop-line|fmax can be solved in O(n3log P)time, where P=maxjrj+∑jpj.