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

孟金涛, 鲁晓旭, 李士生, 周永卫

doi:10.13371/j.cnki.chin.q.j.m.2020.03.007

数学季刊 >

2020 , Vol. 35 >Issue 3: 320 - 330

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2020.03.007

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

展开

1. Zhengzhou University of Aeronautics2. Zhongyuan University of Technology

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.

收稿日期: 2020-02-15

网络出版日期: 2020-10-22

基金资助

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

Expand

1. Zhengzhou University of Aeronautics2. Zhongyuan University of Technology

Received date: 2020-02-15

Online published: 2020-10-22

Supported by

Fold

摘要

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（n²） 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

本文引用格式

孟金涛, 鲁晓旭, 李士生, 周永卫 . 具有工件加工时间相容性和可拒绝的单机分批排序[J]. 数学季刊, 2020 , 35(3) : 320 -330 . DOI: 10.13371/j.cnki.chin.q.j.m.2020.03.007

Abstract

Key words： Batch scheduling; Compatibility; Rejection; Makespan; Approximation algorithm

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract