数学季刊 ›› 2020, Vol. 35 ›› Issue (3): 320-330.doi: 10.13371/j.cnki.chin.q.j.m.2020.03.007

• • 上一篇    

具有工件加工时间相容性和可拒绝的单机分批排序

  

  1. 1. Zhengzhou University of Aeronautics2. Zhongyuan University of Technology
  • 收稿日期:2020-02-15 出版日期:2020-09-30 发布日期:2020-10-22
  • 作者简介:MENG Jintao(1980-), male, native of Luohe, Henan, an associte professor of Zhengzhou University of Aeronautics, M.S., engages in the scheduling theory and its applications;LU Xiaoxu(1975-), male, native of Xuchang, Henan, an associte professor of Zhengzhou University of Aeronautics, Ph.D., engages in network optimization;LI Shisheng(1982-), male, native of Nanyang, Henan, an associte professor of Zhongyuan University of Technology, Ph.D., engages in the scheduling theory and its applications;ZHOU Yongwei(1978-), male, native of Zhoukou, Henan, Professor of Zhengzhou University of Aeronautics, M.S., engages in network optimization.
  • 基金资助:
    Supported by Key Research Projects of Henan Higher Education Institutions (20A110037)； Young Backbone Teachers Training Program of Zhongyuan University of Technology (2018XQG15)； Outstanding Youth Foundation of Science and Technology Innovation of Henan Province (184100510004)； Natural Science Foundation of Henan Education Department (16A630061)； Science and Technology Program of Henan Province(182102110129)； Innovation Training Program for College Students of Henan Province (S201910485026)； Basic Research Projects of Key Scientific Research Projects Plan in Henan Higher Education Institutions(20zx003)；

Batch Scheduling with Job Processing Time Compatibility and Rejection on a Single Machine

  1. 1. Zhengzhou University of Aeronautics2. Zhongyuan University of Technology
  • Received:2020-02-15 Online:2020-09-30 Published:2020-10-22
  • About author:MENG Jintao(1980-), male, native of Luohe, Henan, an associte professor of Zhengzhou University of Aeronautics, M.S., engages in the scheduling theory and its applications;LU Xiaoxu(1975-), male, native of Xuchang, Henan, an associte professor of Zhengzhou University of Aeronautics, Ph.D., engages in network optimization;LI Shisheng(1982-), male, native of Nanyang, Henan, an associte professor of Zhongyuan University of Technology, Ph.D., engages in the scheduling theory and its applications;ZHOU Yongwei(1978-), male, native of Zhoukou, Henan, Professor of Zhengzhou University of Aeronautics, M.S., engages in network optimization.
  • Supported by:
    Supported by Key Research Projects of Henan Higher Education Institutions (20A110037)； Young Backbone Teachers Training Program of Zhongyuan University of Technology (2018XQG15)； Outstanding Youth Foundation of Science and Technology Innovation of Henan Province (184100510004)； Natural Science Foundation of Henan Education Department (16A630061)； Science and Technology Program of Henan Province(182102110129)； Innovation Training Program for College Students of Henan Province (S201910485026)； Basic Research Projects of Key Scientific Research Projects Plan in Henan Higher Education Institutions(20zx003)；

PDF (PC)

161

摘要： We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine. The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint. Three problems are considered:（1） minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;（2） minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;（3） minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O（n2） time algorithm for the first problem. Moreover, for the other two problems, we first show that they are N P-hard, and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them, respectively. 

关键词: Batch scheduling, Compatibility, Rejection, Makespan, Approximation algorithm

Abstract: We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine. The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint. Three problems are considered:（1） minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;（2） minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;（3） minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O（n2） time algorithm for the first problem. Moreover, for the other two problems, we first show that they are N P-hard, and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them, respectively. 

Key words: Batch scheduling, Compatibility, Rejection, Makespan, Approximation algorithm

中图分类号: 

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn