Job Shop Problem

Introduction to Job Shop Problem

We are given a number of jobs and machines. Each job constitutes a sequence of tasks which need to be performed in a particular order. Each task can be processed on a specific machine. We need to schedule all the tasks in such a way that total time to perform all jobs is reduced. This total time to complete all jobs(from the start of the first job to the end of the last job) is also called makespan, hence, we can also say that we want to reduce the makespan of the jobs. This problem is an optimization problem. Similar problems include Activity Selection problem and Job Scheduling problem.

Constraints

There are certain constraints that must hold true while solving this problem:

• All the tasks for a job must be performed in the specific order that is, no task for a job can be started until the previous task for that job is completed.
• A machine can work only on one task at a time.
• A task once started must be completed in entirety.

Factors affecting the solution

These are some of the factors that affect the solution, generally:

• Arrival pattern
• Type of work sequence
• Number of available machines
• Sequence of tasks for each job
• Performance evaluation criterion

Arrival Pattern

The arrival pattern of jobs are categorized into two types:

• Static — n jobs arrive at an idle shop all at once.
• Dynamic — intermittent arrival i.e more jobs are expected after the arrival of the first set of jobs.

Type of work sequence

• Fixed/Repeated sequence - When this happens the problem is slightly modified and is called the Flow Sop Problem. We will discuss about the flow shop problem in a separate article in detail.
• Random sequence

Performance evaluation criterion

Following are some metrics on which the performance of the solution are measured:

• Makespan — total time to complete all jobs. We wish to reduce the makespan.
• Average time of jobs in shop - Total time spent by the job in the shop, including the waiting time. We wish to reduce this.
• Lateness
• Average number of jobs in shop - Average number of jobs being processed at any instant.
• Utilization of machines - Measure of efficiency of the shop. Ratio of total time invested in processing the tasks to the time for which the machines were available but not used for processing. We wish to maximize this.

N Jobs, 1 Machine

Schedule jobs according to their duration starting with the shortest job first.

N Jobs, 2 Machines (Johnson's Rule)

This is one approach to solve the job shop problem. It is used to schedule jobs in 2 work centers(machines). It is used to find the optimal sequence that reduces the makespan. It also reduces the idle time and improves performance.
Following are some prerequisites which should be met before applying this rule:

• The time for each job must be constant.
• Jobs must be mutually exclusive of the job sequence.
• All jobs must be processed in the first machine before going to the second machine and so on.
• All jobs must have equal priority.

After successfully meeting the above conditions, we can apply Johnson's rule.
According to Johnson's rule:

• List the jobs and their duration at each machine.
• Select the job with the shortest time. If the time is associated with the first machine, schedule the job first. Else if, the time is associated with the second machine, schedule it at the end. Break ties arbitrarily.
• Eliminate the shortest job from further consideration.
• Repeat steps 2 and 3 until all jobs have been scheduled.

Example:
Consider 5 jobs each consisting of 2 tasks. The time required (in hrs) for each machine is mentioned below.

Jobs	Machine 1	Machine 2
A	4	3
B	1	2
C	5	4
D	2	3
E	5	6

We use a Gantt chart, which is a diagrammatic aid used widely for scheduling problems. Here, as we need to schedule 5 jobs we will choose a Gantt chart with 5 vacancies. The Gantt chart will be filled by scheduling all the 5 jobs and assigning each job a place in the Gantt chart.
Gantt chart :

1	2	3	4	5
X	X	X	X	X

Initially, all places are empty.

The shortest time is for Job B (1 hr) and is associated with the first machine, so B is scheduled in the beginning. Remove B from further consideration.

1	2	3	4	5
B	X	X	X	X

The shortest time now is for Job D(2 hrs) and it is associated with the first machine, so D is scheduled next at the beginning of the Gantt chart. Remove D from further consideration.

1	2	3	4	5
B	D	X	X	X

The shortest duration is for Job A(3 hrs) and it is associated with the second machine, so A is scheduled at the end of the Gantt chart. Remove A from further consideration.

1	2	3	4	5
B	D	X	X	A

The shortest duration is for JOb C(4 hrs) and it is associated with the second machine, so C is scheduled at the end of the Gantt chart. Remove C from further consideration.

1	2	3	4	5
B	D	X	C	A

Now, only E remains to be scheduled, so we schedule it at the vacant spot.

1	2	3	4	5
B	D	E	C	A

The resulting sequence is : B -> D -> E -> C -> A. The jobs must be scheduled in this sequence on both the machines for optimal performance.
The total makespan is equal to 21 hrs. Machine 1 is not idle whereas Machine 2 is idle for 2 hrs.

N Jobs, M Machines

In this case, the number of cases can be extremely large, of the order (n!)^m. Hence, in this case, there is a strong need of heuristics basis which we can filter out some choices out of all that are possible. Following is a list of popular heuristics which can be used to obtain the optimal solution.

• R (Random) – Pick any Job in queue with equal probability. This rule is often used as benchmark for other rules. This heuristic, surprisingly, has a very good performance.
• FCFS (First Come First Serve) – Jobs are processed in the order in which they arrive at the machine(also known as earliest release date)
• SPT (Shortest Processing Time) – This rule tends to reduce both work-in-process
  inventory, the average job completion (flow) time, and average job lateness.
• EDD (Earliest Due Date) – The Job with earliest due date is chosen.
• CR (Critical Ratio) = Processing Time / Time until due (Due Date – Current Time) -
  Take the highest value.
• LWR (Least Work Remaining) – This rule is an extension of SPT variant that considers the number of successive operations.
• ST (Slack Time) = Time until job is due - (Sum of processing time remaining). Take the job with the smallest amount of slack time.
• ST/O (Slack Time per Remaining Operation) = slack time divided by number of
  operations remaining. Take the job with the smallest amount of slack time per remaining operation
  When in Doubt, use SPT. Also, use SPT to break ties.