Job shop scheduling

From Wikipedia, the free encyclopedia
  (Redirected from Job-shop problem)
Jump to: navigation, search
For other uses, see 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 J1J2, ..., Jn of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Nowadays, the problem is presented as an online problem (dynamic scheduling), that is, each job is presented, and the online algorithm needs to make a decision about that job before the next job is presented.

This problem is one of the best known online problems, and was the first problem for which competitive analysis was presented, by Graham in 1966.[1] Best problem instances for basic model with makespan objective are due to Taillard.[2]

Problem variations[edit]

Many variations of the problem exist, including the following:

  • Machines can be related, independent, equal
  • Machines can require a certain gap between jobs or no idle-time
  • Machines can have sequence-dependent setups
  • Objective function can be to minimize the makespan, the Lp norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem
  • Jobs may have constraints, for example a job i needs to finish before job j can be started (see workflow). Also, the objective function can be multi-criteria.[3]
  • Jobs and machines have mutual constraints, for example, certain jobs can be scheduled on some machines only
  • Set of jobs can relate to different set of machines
  • Deterministic (fixed) processing times or probabilistic processing times
  • There may also be some other side constraints

NP-hardness[edit]

If one already knows that the travelling salesman problem is NP-hard (as it is), then the job-shop problem is clearly also NP-hard, since the TSP is special case of the JSP with m = 1 (the salesman is the machine and the cities are the jobs).

Problem representation[edit]

The disjunctive graph [4] is one of the popular models used for describing the job shop scheduling problem instances.[5]

A mathematical statement of the problem can be made as follows:

Let M = \{ M_{1}, M_{2}, \dots, M_{m} \} and J = \{ J_{1}, J_{2}, \dots, J_{n} \} be two finite sets. On account of the industrial origins of the problem, the \displaystyle M_{i} are called machines and the \displaystyle J_{j} are called jobs.

Let \displaystyle \ \mathcal{X} denote the set of all sequential assignments of jobs to machines, such that every job is done by every machine exactly once; elements x \in \mathcal{X} may be written as n \times m matrices, in which column \displaystyle i lists the jobs that machine \displaystyle M_{i} will do, in order. For example, the matrix

x = \begin{pmatrix} 1 & 2 \\ 2 & 3 \\ 3 & 1 \end{pmatrix}

means that machine \displaystyle M_{1} will do the three jobs \displaystyle J_{1}, J_{2}, J_{3} in the order \displaystyle J_{1}, J_{2}, J_{3}, while machine \displaystyle M_{2} will do the jobs in the order \displaystyle J_{2}, J_{3}, J_{1}.

Suppose also that there is some cost function C : \mathcal{X} \to [0, + \infty]. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times C_{ij} : M \times J \to [0, + \infty], the cost/time for machine \displaystyle M_{i} to do job \displaystyle J_{j}.

The job-shop problem is to find an assignment of jobs x \in \mathcal{X} such that \displaystyle C(x) is a minimum, that is, there is no y \in \mathcal{X} such that \displaystyle C(x) > C(y).

The problem of infinite cost[edit]

One of the first problems that must be dealt with in the JSP is that many proposed solutions have infinite cost: i.e., there exists x_{\infty} \in \mathcal{X} such that C(x_{\infty}) = + \infty. In fact, it is quite simple to concoct examples of such x_{\infty} by ensuring that two machines will deadlock, so that each waits for the output of the other's next step.

Major results[edit]

Graham had already provided the List scheduling algorithm in 1966, which is (2 − 1/m)-competitive, where m is the number of machines.[1] Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. The Coffman–Graham algorithm (1972) for uniform-length jobs is also optimum for two machines, and is (2 − 2/m)-competitive.[6][7] In 1992, Bartal, Fiat, Karloff and Vohra presented an algorithm that is 1.986 competitive.[8] A 1.945-competitive algorithm was presented by Karger, Philips and Torng in 1994.[9] In 1992, Albers provided a different algorithm that is 1.923-competitive.[10] Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.[11]

A lower bound of 1.852 was presented by Albers.[12] Taillard instances has an important role in developing job shop scheduling with makespan objective.

In 1976 Garey provided a proof[13] that this problem is NP-complete for m>2, that is, no optimal solution can be computed in polynomial time for three or more machines (unless P=NP).

Offline makespan minimization[edit]

Atomic jobs[edit]

The simplest form of the offline makespan minimisation problem deals with atomic jobs, that is, jobs that are not subdivided into multiple operations. It is equivalent to packing a number of items of various different sizes into a fixed number of bins, such that the maximum bin size needed is as small as possible. (If instead the number of bins is to be minimised, and the bin size is fixed, the problem becomes a different problem, known as the bin packing problem.)

Hochbaum and Shmoys presented a polynomial-time approximation scheme in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.[14]

Jobs consisting of multiple operations[edit]

The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc., and a single job cannot be performed in parallel, is known as the open shop scheduling problem. Various algorithms exist, including genetic algorithms.[15]

Johnson's algorithm[edit]

See also: Johnson's rule

A heuristic algorithm by S. M. Johnson can be used to solve the case of a 2 machine N job problem when all jobs are to be processed in the same order.[16] The steps of algorithm are as follows:

Job Pi has two operations, of duration Pi1, Pi2, to be done on Machine M1, M2 in that sequence.

  • Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.
  • Step 2. From all available operation durations, pick the minimum.

If the minimum belongs to Pk1,

Remove K from list A; Add K to end of List L1.

If minimum belongs to Pk2,

Remove K from list A; Add K to beginning of List L2.

  • Step 3. Repeat Step 2 until List A is empty.
  • Step 4. Join List L1, List L2. This is the optimum sequence.

Johnson's method only works optimally for two machines. However, since it is optimal, and easy to compute, some researchers have tried to adopt it for M machines, (M > 2.)

The idea is as follows: Imagine that each job requires m operations in sequence, on M1, M2 … Mm. We combine the first m/2 machines into an (imaginary) Machining center, MC1, and the remaining Machines into a Machining Center MC2. Then the total processing time for a Job P on MC1 = sum( operation times on first m/2 machines), and processing time for Job P on MC2 = sum(operation times on last m/2 machines).

By doing so, we have reduced the m-Machine problem into a Two Machining center scheduling problem. We can solve this using Johnson's method.

Example[edit]

Here is an example of a job shop scheduling problem formulated in AMPL as a mixed-integer programming problem with indicator constraints:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 3;

param ProcessingTime:
  1 2 3 :=
1 4 2 1
2 3 6 2
3 7 2 3
4 1 5 8;

See also[edit]

References[edit]

  1. ^ a b Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal 45: 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. 
  2. ^ "Taillard Instances". 
  3. ^ Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5. 
  4. ^ B. Roy, B. Sussmann, Les problèmes d’ordonnancement avec constraintes disjonctives, SEMA, Note D.S., No. 9, Paris, 1964.
  5. ^ Jacek Bl̶ażewicz, Erwin Pesch, Mal̶gorzata Sterna, The disjunctive graph machine representation of the job shop scheduling problem, European Journal of Operational Research, Volume 127, Issue 2, 1 December 2000, Pages 317-331, ISSN 0377-2217, 10.1016/S0377-2217(99)00486-5.
  6. ^ Coffman, E. G., Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems", Acta Informatica 1: 200–213, doi:10.1007/bf00288685, MR 0334913 .
  7. ^ Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing 6 (3): 518–536, doi:10.1137/0206037, MR 0496614 .
  8. ^ Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "Proc. 24th ACM Symp.". Theory of Computing. pp. 51–58. doi:10.1145/129712.129718.  |chapter= ignored (help)
  9. ^ Karger, D.; S. Phillips; E. Torng (1994). "Proc. Fifth ACM Symp.". Discrete Algorithms.  |chapter= ignored (help)
  10. ^ Albers, Susanne; Torben Hagerup (1992). "Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms". Symposium on Discrete Algorithms archive. pp. 463–472.  |chapter= ignored (help)
  11. ^ Fleischer, Rudolf (2000). Algorithms - ESA 2000. Berlin / Heidelberg: Springer. pp. 202–210. ISBN 978-3-540-41004-1. 
  12. ^ Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal on Computing 29 (2): 459–473. doi:10.1137/S0097539797324874. 
  13. ^ Garey, M.R. (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research 1 (2): 117–129. doi:10.1287/moor.1.2.117. JSTOR 3689278. 
  14. ^ Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM 34 (1): 144–162. doi:10.1145/7531.7535. 
  15. ^ Khuri, Sami; Miryala, Sowmya Rao (1999). "Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence". London: Springer Verlag. CiteSeerX: 10.1.1.29.4699.  |chapter= ignored (help)
  16. ^ S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

External links[edit]