mean completion time (the average of over all j), which is sometimes denoted by mft (mean finish time). : The flow time of a job is difference between its completion time and its release time, i.e. . : Lateness. Every job is given a due date . The lateness of job is defined as . Sometimes is used to denote feasibility for a problem with deadlines. Indeed using binary search, the complexity of the feasibility version is equivalent to the minimization of . : Throughput. Every job is given a due date . There is a unit profit for jobs that complete on time, i.e. if and otherwise. Sometimes the meaning of is inverted in the literature, which is equivalent when considering the decision version of the problem, but which makes a huge difference for approximations. : Tardiness. Every job is given a due date . The tardiness of job is defined as . : Earliness. Every job is given a due date . The earliness of job is defined as . This objective is important for just-in-time scheduling. There are also variants with multiple objectives, but they are much less studied. Examples Here are some examples for problems defined using the above notation. – assigning each of given jobs to one of the two identical machines so to minimize the maximum total processing time over the machines. This is an optimization version of the partition problem 1|prec| – assigning to a single machine, processes with general precedence constraint, minimizing maximum lateness. R|pmtn| – assigning tasks to a variable number of unrelated parallel machines, allowing preemption, minimizing total completion time. J3| – a 3-machine job shop problem with unit processing times, where the goal is to minimize the maximum completion time. – assigning jobs to parallel identical machines, where each job comes with a number of machines on which it must be scheduled at the same time, minimizing maximum completion time. See parallel task scheduling. Other variants All variants surveyed above are deterministic in that all data is known to the planner. There are also stochastic variants, in which the data is not known in advance, or can perturb randomly. External links Scheduling zoo (by Christoph Dürr, Sigrid Knust, Damien Prot, Óscar C. Vásquez): an online tool for searching an optimal scheduling problem using the notation. Complexity results for scheduling problems (by Peter Brucker, Sigrid Knust): a classification of optimal