Бір машинада тапсырмаларды жоспарлау мәселесі

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||" is an single machine scheduling problem with no constraints, where the goal is to minimize the sum of completion times. The makespan minimization problem 1||, 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.

The problem 1|| 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
The problem 1|| 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 presents both exact exponential time algorithms and a polynomial time approximation algorithm.

The problem 1|| aims to minimize the number of late jobs, regardless of the amount of lateness. It can be solved optimally by the Hodgson Moore algorithm. The unweighted optimization variant, maximizing the number of jobs that finish on time, denoted 1||, can be solved in time using dynamic programming, when all release times and deadlines are integers. The decision variant deciding whether it is possible that all given jobs complete on time can be solved by several algorithms, the fastest of them runs in time
Jobs can have execution intervals. For each job j, there is a processing time tj and a start time sj, so it must be executed in the interval [sj, sj+tj]. Since some of the intervals overlap, not all jobs can be completed. The goal is to maximize the number of completed jobs, that is, the throughput. More generally, each job may have several possible intervals, and each interval may be associated with a different profit. The goal is to choose at most one interval for each job, such that the total profit is maximized. For more details, see the page on interval scheduling. More generally, jobs can have time windows, with both start times and deadlines, which may be larger than the job length. Each job can be scheduled anywhere within its time window. Bar Noy, Bar Yehuda, Freund, Naor and Schieber 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 both cases, the length (processing time) of a job is not constant, but depends on the jobs processed before it. In this setting, even minimizing the maximum completion time becomes non trivial. There are two common ways to model the change in job length. The job length may depend on the start time of the job. When the length is a weakly increasing function of the start time, it is deterioration effect; when it is weakly decreasing, it is called learning effect. The job length may depend on the sum of normal processing times of previously processed jobs. When the length is a weakly increasing function of this sum, it is often called aging effect.