Scheduling Models With Jobs' Processing Times Being Nonconstant

Scheduling is a class of important combinational optimization problem. In the classical scheduling, it is assumed that the processing times of jobs are constant. However, there are many real-life situation where the processing times of jobs depend on machinery facilities, their starting processed times or their position positions being processed. Basing on those reasons, a class of new scheduling problems put forward-scheduling problems with jobs' processing times being nonconstant. In general, such a class of modern scheduling problems is more complex than classical scheduling problems, for most of them are NP—hard problems. For these NP-hard problems, it is necessary that some approximation algorithms are constructed, and their worst-case bounds are analyzed. At the same time, considering the requirement of practical application, polynomial time algorithms are also necessary for some of these modern scheduling problems. For on the one hand, the polynomial time algorithms can be used to solve some specialcases of the NP — hard problem, on the other hand, these polynomial algorithms can be used as approximation algorithms for the original NP — hard problem. This paper mainly considers such a class of new modern scheduling problems with jobs having non-constant processing times, the contributions can be summarized as follows:1. This paper introduces the basic concepts of scheduling problems, computational complexity, heuristic algorithms and worst-case ratio, and the main results related to jobs' processing times being non-constant.2. For the scheduling models with jobs' processing times are linear function of their normal processing times and starting times.(1) For the single machine scheduling problems with minimizing the makespan, the optimal algorithms are given.For the single machine scheduling p[roblem with minimizing weighted total flow time, we prove it is an NP-hard problem.(2) For the flow shop scheduling problems, under the constraint of no-idle dominant machines, corresponding to the objective functions, makespan and the total flow time, the optimal algorithms are given3. For the scheduling models with jobs' processing times are linear function of their starting times.