Modern Scheduling Jobs With Varying Processing Times

Scheduling is an important combinatorial optimization problem. In the classical scheduling it is assumed that the processing times of jobs are constant values. However, there are many situations where the processing time of the job depends on its starting time, its resource allocation or its position in the sequence. From this, the modern scheduling problems emerged. The modern scheduling problems are more complex than classical scheduling problems, most of which are NP-hard problems. For these NP-hard problems, it is necessary that approximation algorithms are given, and the worst-case bounds are analyzed. Considering the requirement of practical application, the cases of modern scheduling problems which are polynomial time algorithms are also necessary. On one side the polynomial time algorithms can be used to solve some problems, on other side the algorithms can be considered as approximation algorithms of other problems. This paper considers modern scheduling jobs with varying processing times, the main contributions can be summarized as follows:1. Chapter 2. Job processing time being a increasing function of the starting time scheduling problems.(a) Maximum makespan single machine scheduling problems. For the general model with rooted forest precedence constraints jobs or series-parallel digraphs jobs, the optimal algorithms are presented.(b) The weighted sum of completion times single machine scheduling problems. For the special model of the basic processing is related to increasing rate with rooted forest precedence constraints jobs or series-parallel digraphs jobs, the optimal algorithms are presented.(c) Flow shop scheduling problems. The cases where the machines satisfying some dominance relations and no-wait or no-idle are discussed, and some solutions are given.2. Chapter 3. Job processing time being a decreasing function of the starting time scheduling problems. For the case of the basic processing is related to decreasing rate:(a) Single machine scheduling problems. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, weighted sum ofcompletion times, weighted sum of completion times of chains precedence constraints. maximum cost and maximum lateness.(b) Flow shop scheduling problems. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. The cases where the basic processing times of operations are equal for each job, and some solutions are given.3. Chapter 4. Single machine scheduling problems with controllable processing times.First, we consider the general controllable processing times problem. We concentrate on three goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost; minimizing a cost function containing earliness, tardiness, due dates and compressions. The problem is modelled as an assignment problem respectively, and thus can be solved with the well-known algorithms. Second, we consider the discretely controllable processing times problems. We consider some multi-criteria scheduling, the problems are modelled as an assignment problem.4. Chapter 5. Scheduling problems with a learning effect.For single machine scheduling, we consider some multi-criteria scheduling, the problems are modelled as an assignment problem. For flow shop scheduling. An example is constructed to show that the classical Johnson's rule is not the optimal solution for the two-machine flow shop scheduling to minimize makespan with a learning effect. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. For the m-machine, a heuristic algorithm with worst-case bound m for makespan or the sum of completion t...