We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on a single machine, in a way that optimizes a certain objective, such as the throughput.
Many problems, which are NP-hard in general, can be solved in polynomial time in the single-machine case.
[1]: 10–20 In the standard three-field notation for optimal job scheduling problems, the single-machine variant is denoted by 1 in the first field.
" is a single-machine scheduling problem with no constraints, where the goal is to minimize the sum of completion times.
It can be solved optimally by the Shortest Processing Time First rule (SPT): the jobs are scheduled by ascending order of their processing time
aims to minimize the weighted sum of completion times.
It can be solved optimally by the Weighted Shortest Processing Time First rule (WSPT): the jobs are scheduled by ascending order of the ratio
is a generalization of the above problem for jobs with dependencies in the form of chains.
If it is completed after its due date, it suffers lateness defined as
can be solved optimally by the Earliest Due Date First rule (EDD): the jobs are scheduled by ascending order of their deadline
in two ways: first, it allows arbitrary precedence constraints on the jobs; second, it allows each job to have an arbitrary cost function hj, which is a function of its completion time (lateness is a special case of a cost function).
The presence of release times means that, in some cases, it may be optimal to leave the machine idle, in order to wait for an important job that is not released yet.
Minimizing maximum lateness in this setting is NP-hard.
It is NP-hard, since the special case in which all jobs have the same deadline (denoted by 1|
However, when all job lengths are equal, the problem can be solved in polynomial time.
The goal is to maximize the number of completed jobs, that is, the throughput.
The goal is to choose at most one interval for each job, such that the total profit is maximized.
Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber[10] present a (1-ε)/2 approximation.
Workers and machines often become tired after working for a certain amount of time, and this makes them slower when processing future jobs.
On the other hand, workers and machines may learn how to work better, and this makes them faster when processing future jobs.
In this setting, even minimizing the maximum completion time becomes non-trivial.
There are two common ways to model the change in job length.
Cheng and Ding studied makespan minimization and maximum-lateness minimization when the actual length of job j scheduled at time sj is given by
Kubiak and van-de-Velde[16] studied makespan minimization when the fatigue starts only after a common due-date d. That is, the actual length of job j scheduled at time sj is given by
They show that the problem is NP-hard, give a pseudopolynomial algorithm that runs in time
, and give a branch-and-bound algorithm that solves instances with up to 100 jobs in reasonable time.
They also study bounded deterioration, where pj stops growing if the job starts after a common maximum deterioration date D > d. For this case, they give two pseudopolynomial time algorithms.
Cheng, Ding and Lin[11] surveyed several studies of a deterioration effect, where the length of job j scheduled at time sj is either linear or piecewise linear, and the change rate can be positive or negative.
Here, f is an increasing function that describes the dependance of the fatigue on the processing time; and αj is the aging characteristic of job j.
For this model, he proved the following results: Many solution techniques have been applied to solving single machine scheduling problems.