English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (1): 131-139.doi: 10.15960/j.cnki.issn.1007-6093.2020.01.010

• • 上一篇    下一篇

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

刘晓霞, 余山杉, 罗文昌*   

  1. 宁波大学数学与统计学院, 浙江宁波 315211
  • 收稿日期:2019-06-03 发布日期:2020-03-09
  • 通讯作者: 罗文昌 E-mail:luowenchang@163.com
  • 基金资助:
    国家自然科学基金（No.11971252），浙江省自然科学基金（No.LY19A010005）

Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold

LIU Xiaoxia, YU Shanshan, LUO Wenchang*   

  1. School of Mathematics and Statistics, Ningbo University, Ningbo 315211, Zhejiang, China
  • Received:2019-06-03 Published:2020-03-09

PDF

134

摘要： 考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中，给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间；对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工；一个工件如果被拒绝，则需支付该工件对应的拒绝费用.为了保证一定的服务水平，要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的，对此给出了伪多项式时间动态规划精确算法，2-近似算法和完全多项式时间近似方案.

关键词: 平行分批排序, 拒绝, 动态规划, 近似算法

Abstract: In this paper, we consider the single machine parallel-batch scheduling problem with release dates and the number of rejected jobs not exceeding a given threshold. In this problem, we are given a set of jobs and a parallel batch processing machine. Each job has its release date and processing time; for each job, it is either to be rejected or to be accepted and processed in some batch on the machine. If one job is rejected then its corresponding rejection cost should be paid. To keep a certain service level, it is required that the number of rejected jobs is not greater than a given threshold. The task is how to partition the rejected jobs and the accepted jobs with the given constraint, and determine the batches and the orders for the accepted jobs on the machine to minimize the sum of the makespan and the total rejection cost. Since the studied problem is NP-hard, we propose a pseudo-polynomial time dynamic programming exact algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme.

Key words: parallel-batch scheduling, rejection, dynamic programming, approximation algorithm

中图分类号: