Job Shop Scheduling
Job shop scheduling (or job-shop problem) is an optimization problem in computer science and operations research in which ideal jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). In most practical settings, the problem is presented as an online problem (dynamic scheduling), that is, the decision of scheduling a job can only be made online, when the job is presented to the algorithm.
This problem is one of the best known combinatorial optimization problems, and was the first problem for which competitive analysis was presented, by Graham in 1966. Best problem instances for basic model with makespan objective are due to Taillard.
Many variations of the problem exist, including the following:
Since the travelling salesman problem is NP-hard, the job-shop problem with sequence-dependent setup is clearly also NP-hard, since the TSP is a special case of the JSP with (the salesman is the machine and the cities are the jobs).
The disjunctive graph is one of the popular models used for describing the job shop scheduling problem instances.
A mathematical statement of the problem can be made as follows:
...
Wikipedia