• •

### 关于总加权提前损失的单机排序问题

1. 1. 重庆师范大学数学科学学院, 重庆 401331; 2. 重庆育才中学, 重庆 400050
• 出版日期:2018-04-25 发布日期:2021-06-29

LI Ping, ZHANG Xingong, WAN Qing. Single Machine Scheduling Problem with Minimize Total Weighted Early Work[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41(4): 1068-1078.

### Single Machine Scheduling Problem with Minimize Total Weighted Early Work

LI Ping1 ,ZHANG Xingong1, WAN Qing2

1. 1. School of Mathematical Science, Chongqing Normal University, Chongqing 401331; 2. Chongqing Yucai High School, Chongqing 400050
• Online:2018-04-25 Published:2021-06-29

In this paper, we consider the single machine scheduling problem to minimize the total weighted early work. The early work of a job is a duration of the parts of the job completed prior to its due-date. First, this paper analyzes the complexity of the total weighted early work problem with preemptive case, and proposes an Interruption Scheduling Algorithm. Second, the problem without preemptive case is illustrated to be NP-hard by designing a quasi-polynomial dynamic programming algorithm, and data experiments are performed to verify the effectiveness of the algorithm.
()
 No related articles found!