Advanced Search
    Li Xiuqian, Feng Haodi, Su Zheng. Batch Scheduling to Minimize the Sum of Total Completion Time Plus the Sum of Total Penalties[J]. Journal of Computer Research and Development, 2013, 50(8): 1700-1709.
    Citation: Li Xiuqian, Feng Haodi, Su Zheng. Batch Scheduling to Minimize the Sum of Total Completion Time Plus the Sum of Total Penalties[J]. Journal of Computer Research and Development, 2013, 50(8): 1700-1709.

    Batch Scheduling to Minimize the Sum of Total Completion Time Plus the Sum of Total Penalties

    • Recently, quite a few works focus on single machine parallel batch scheduling problem with penalties. While most of them concern the makespan objective, little effort is put into the total completion time, which is studied in this paper. We study the following single machine parallel batch scheduling problem: There are n given jobs. Each job has a processing time and a rejection penalty (Some job may be rejected for processing. Some rejection penalty is paid if a job is rejected). There is a single parallel batch machine that can process at most b jobs simultaneously. The jobs processed together form a batch. All jobs processed in the same batch have the same start time and the same completion time, that is, the start time plus the maximum processing time over all the jobs in the batch. We need to determine how to choose jobs for processing, divide these jobs into batches, and sequence these batches so that the sum of completion time of the processed jobs plus the sum of rejection penalties of the rejected ones is minimized. We give an O((b2-b)×n2b2-2b+2×bb2-b-1)-time dynamic programming algorithm, and thus conclude that this problem can be solved in polynomial time when the batch size b is fixed.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return