Description of Job Shop Scheduling

The n x m JSSP can be described by a set of n jobs {J_i} _{1≤ i ≥ n} which is to be processed on a set of m machines {M_k} _{1≤ k ≥ m} in a technological sequence of machines. The processing of job J_i on machine M_k for an uninterrupted duration {T_ik}_{1≤ i ≥ n, 1≤ k ≥ m} called processing time and completion times for each operation {E_ik}_{1≤ i ≥ n, 1≤ k ≥ m} that satisfies constraints. The time required to complete all the jobs is called the make-span C_max and is equal to E_im. The objective is to optimizing this general problem to determine the schedule which minimizes C_max. The Conceptual model of JSSP can be describes as below:

1. Objective function

1. C_max* = Min(C_max)

1. Subject to:

1. E_ik ≥ E_i(k-1)+T_ik

2. E_ik ≥ E_(i-1)k+T_ik

3. E_ik ≥ 0

Where i=1, …, n and k=1, …, m

Thus the (1) objective function is minimizes the make-span and (2) constraints, impose the precedence relations between operations and finally forces the completion time to be non-negative.

Related Posts:

• JOB SHOP SCHEDULING
• Assumptions in static JSSP
• Johnson’s Rule
• Algorithm of Johnson’s Rule
• Illustration for Johnson’s rule
• Modified Johnson’s Rule for n x m JSSP
• Limitations of Johnson’s Rule
• What makes scheduling problems hard?

Table of Contents

© 2006 Kumaravel & Project Team