Parallel-batch scheduling with deterioration and rejection on a single machine  

作　　者：LI Da-wei LU Xi-wen 

机构地区：[1]School of Science,East China University of Science and Technology,Shanghai 200237,China.

出　　处：《Applied Mathematics(A Journal of Chinese Universities)》2020年第2期141-156,共16页高校应用数学学报（英文版）（B辑）

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

摘　　要：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.

关 键 词：parallel-batch scheduling REJECTION DETERIORATION FPTAS NP-COMPLETE 

分 类 号：O221[理学—运筹学与控制论] F273[理学—数学]