Please wait a minute...
Applied Mathematics-A Journal of Chinese Universities  2020, Vol. 35 Issue (2): 141-156    DOI: 10.1007/s11766-020-3624-2
    
Parallel-batch scheduling with deterioration and rejection  on a single machine#br#
LI Da-wei, LU Xi-wen
School of Science, East China University of Science and Technology, Shanghai 200237, China.
Parallel-batch scheduling with deterioration and rejection  on a single machine
LI Da-wei, LU Xi-wen
School of Science, East China University of Science and Technology, Shanghai 200237, China.
 全文: PDF 
摘要： The single machine parallel-batch scheduling with deteriorating jobs and rejection
is considered in this paper. A job is either rejected, in which a rejection penalty should be paid,
or accepted and processed on the machine. Each job’s processing time is an increasing linear
function of its starting time. The machine can process any number of jobs simultaneously as a
batch. The processing time of a batch is equal to the largest processing time of the jobs in the
batch. The objectives are to minimize the makespan and the total weighted completion time,
respectively, under the condition that the total rejection penalty cannot exceed a given upper
bound Q. We show that both problems are NP-complete and present dynamic programming
algorithms and fully polynomial time approximation schemes (F P T ASs) for the considered
problems.
关键词： parallel-batch scheduling;  rejection;  deterioration;  F P T AS;  NP-complete    
Abstract: The single machine parallel-batch scheduling with deteriorating jobs and rejection
is considered in this paper. A job is either rejected, in which a rejection penalty should be paid,
or accepted and processed on the machine. Each job’s processing time is an increasing linear
function of its starting time. The machine can process any number of jobs simultaneously as a
batch. The processing time of a batch is equal to the largest processing time of the jobs in the
batch. The objectives are to minimize the makespan and the total weighted completion time,
respectively, under the condition that the total rejection penalty cannot exceed a given upper
bound Q. We show that both problems are NP-complete and present dynamic programming
algorithms and fully polynomial time approximation schemes (F P T ASs) for the considered
problems.
Key words: parallel-batch scheduling    rejection    deterioration    F P T AS    NP-complete
出版日期: 2020-06-01
CLC:  90B35  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
LI Da-wei
LU Xi-wen

引用本文:

LI Da-wei, LU Xi-wen. Parallel-batch scheduling with deterioration and rejection  on a single machine#br#[J]. Applied Mathematics-A Journal of Chinese Universities, 2020, 35(2): 141-156.

LI Da-wei, LU Xi-wen. Parallel-batch scheduling with deterioration and rejection  on a single machine. Applied Mathematics-A Journal of Chinese Universities, 2020, 35(2): 141-156.

链接本文:

http://www.zjujournals.com/amjcub/CN/10.1007/s11766-020-3624-2    或    http://www.zjujournals.com/amjcub/CN/Y2020/V35/I2/141

No related articles found!