Affiliation of Author(s):经济与管理学院

Journal:JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION

Key Words:Scheduling total load makespan NP-hard FPTAS

Abstract: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.

ISSN No.:1547-5816

Translation or Not:no

Date of Publication:2018-04-01

Co-author:Yang, Dar-Li,Zhou Dequn,zp

Correspondence Author:Yu Xianyu