MULTI-MACHINE SCHEDULING WITH INTERVAL CONSTRAINED POSITION-DEPENDENT PROCESSING TIMES

被引：0

作者：

Yu, Xianyu ^{[1
]}

Yang, Dar-Li ^{[2
]}

Zhou, Dequn ^{[1
]}

Zhou, Peng ^{[1
]}

机构：

[1] Nanjing Univ Aeronaut & Astronaut, Coll Econ & Management, Nanjing 211106, Jiangsu, Peoples R China

[2] Natl Formosa Univ, Dept Informat Management, Yunlin 63201, Taiwan

来源：

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION | 2018年 / 14卷 / 02期

关键词：

Scheduling; total load; makespan; NP-hard; FPTAS; MINIMIZE TOTAL LOAD; SINGLE-MACHINE; DETERIORATING JOBS; WINDOW CONSTRAINTS; BOUND ALGORITHM; ROBOTIC CELL; MAINTENANCE; ASSIGNMENT; REJECTION; FPTAS;

D O I：

10.3934/jimo.2017076

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper investigates multi-machine scheduling problems with interval constrained actual processing times. The actual processing time of each job is assumed to be restricted in a given interval otherwise the extra earliness or tardiness time should be used to patch up the flaw of job. The objectives are to find the optimal job sequence to minimize the total load of machines, the number of exceeding-interval jobs and the makespan of job schedule, respectively. This paper shows that both of the total load minimization problem and the exceeding job number minimization problem are polynomially solvable. For the makespan minimization problem, this paper proves that it is NP-hard, and proposes a fully polynomial time approximation scheme (FPTAS) for the case with two parallel machines.

引用

页码：803 / 815

页数：13

共 32 条

[1] Single-machine scheduling with learning considerations [J].