文献类型：期刊文献

中文题名：Parallel-batch scheduling with deterioration and rejection on a single machine

英文题名：Parallel-batch scheduling with deterioration and rejection on a single machine

作者：Li, Da-wei[1];Lu, Xi-wen[1]

机构：[1]East China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China

年份：2020

卷号：35

期号：2

起止页码：141

中文期刊名：Applied Mathematics(A Journal of Chinese Universities)

外文期刊名：APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B

收录：;Scopus;WOS:【SCI-EXPANDED(收录号:WOS:000540534500002)】；CSCD:【CSCD2019_2020】；

基金：Supported by the National Natural Science Foundation of China (11871213, 71431004).

语种：英文

中文关键词：parallel-batch scheduling;rejection;deterioration;FPTAS;NP-complete

外文关键词：parallel-batch scheduling; rejection; deterioration; FPTAS; NP-complete

摘要：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(FPTASs)for the considered problems.
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 boundQ. We show that both problems areNP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes (FPTASs) for the considered problems.