Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. 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. Single-machine scheduling is a special case of identical-machines scheduling, which is itself a special case of optimal job scheduling. Many problems, which are NP-hard in general, can be solved in polynomial time in the single-machine case. In the standard three-field notation for optimal job scheduling problems, the single-machine variant is denoted by 1 in the first field. For example, " 1|| ∑ C j {\displaystyle \sum C_{j}} " is a single-machine scheduling problem with no constraints, where the goal is to minimize the sum of completion times. The makespan-minimization problem 1|| C max {\displaystyle C_{\max }} , which is a common objective with multiple machines, is trivial with a single machine, since the makespan is always identical. Therefore, other objectives have been studied.
Minimizing the sum of completion times The problem 1|| ∑ C j {\displaystyle \sum C_{j}} aims 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 p j {\displaystyle p_{j}} . The problem 1|| ∑ w j C j {\displaystyle \sum w_{j}C_{j}} 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 p j / w j {\displaystyle p_{j}/w_{j}} . The problem 1|chains| ∑ w j C j {\displaystyle \sum w_{j}C_{j}} is a generalization of the above problem for jobs with dependencies in the form of chains. It can also be solved optimally by a suitable generalization of WSPT. The problem 1|prec| ∑ w j C j {\displaystyle \sum w_{j}C_{j}} is the precedence-constrained version of the original problem. This problem is known to be strongly NP-hard. A partial order ( N , → ) {\displaystyle (N,\rightarrow )} is defined to model the precedence constrained where N {\displaystyle N} is the set of all jobs. This problem is polynomially solvable for simple classes of posets. There are several approximation algorithms with an approximation factor of 2.
Minimizing the cost of lateness The problem 1|| L max {\displaystyle L_{\max }} aims to minimize the maximum lateness. For each job j, there is a due date d j {\displaystyle d_{j}} . If it is completed after its due date, it suffers lateness defined as L j := C j − d j {\displaystyle L_{j}:=C_{j}-d_{j}} . 1|| L max {\displaystyle L_{\max }} can be solved optimally by the Earliest Due Date First rule (EDD): the jobs are scheduled by ascending order of their deadline d j {\displaystyle d_{j}} . The problem 1|prec| h max {\displaystyle h_{\max }} generalizes the 1|| L max {\displaystyle L_{\max }} 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 maximum cost can be minimized by a greedy algorithm known as Lawler's algorithm. The problem 1| r j {\displaystyle r_{j}} | L max {\displaystyle L_{\max }} generalizes 1|| L max {\displaystyle L_{\max }} by allowing each job to have a different release time by which it becomes available for processing. 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. But in practice, it can be solved using a branch-and-bound algorithm.
… excerpt ends here. Continue reading the full article.
