The bounded parallel-batching scheduling with drop-line jobs to minimize total completion time

Expand
  • 1. School of Mathematics and Statistics, Zhengzhou University,  Zhengzhou 450001, China

Received date: 2017-01-03

  Online published: 2018-03-15

Abstract

In this paper, we consider the bounded parallel-batching scheduling problem with drop-line jobs to minimize the total completion time. In the problem, a parallel-batching machine can handle up to b jobs simultaneously as a parallel batch, where b is the batch capacity, and the processing time of a batch is equal to the longest processing time of the jobs assigned to it. For drop-line jobs, the completion time of each job is equal to the sum of the starting time of the batch containing the job and the processing time of the job. That is, if a batch B has a starting time S, then the starting time of each job J_j contained in batch B is defined to be S, and its completion time is defined as S+p_j, where p_j is the processing time of job J_j. For our problem, we first study some properties of the optimal schedules. Then, based on these properties, we present a dynamic programming algorithm running in O(n^{b (b-1)}) time.

Cite this article

JIU Mingzhu, GAO Yuan, YUAN Jinjiang . The bounded parallel-batching scheduling with drop-line jobs to minimize total completion time[J]. Operations Research Transactions, 2018 , 22(1) : 32 -41 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.01.002

Outlines

/