Combinatorial Structure of Optimal Solutions to the Problem of a Single Machine with Preemption

被引：0

作者：

Chernykh, Kseniya A. ^{[1
]}

Servakh, Vladimir V. ^{[1
]}

机构：

[1] Sobolev Inst Math, Omsk, Russia

来源：

2019 15TH INTERNATIONAL ASIAN SCHOOL-SEMINAR OPTIMIZATION PROBLEMS OF COMPLEX SYSTEMS (OPCS 2019) | 2019年

关键词：

scheduling theory; single-stage systems; preemption;

D O I：

10.1109/opcs.2019.8880148

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

The problem of minimizing the weighted average time to complete jobs on a single machine is considered. The release dates of jobs are fixed. The preemptions are possible. The processing times of all jobs are equal. The computational complexity this problem is unknown. An approach to the analysis of the structure of the optimal solutions is proposed. Polynomial algorithms are described for some important classes.

引用

页码：21 / 26

页数：6