Page 293 - DMGT206_PRODUCTION_AND_OPERATIONS_MANAGEMENT

Production and Operations Management

Notes 14.4 Job Shop Scheduling

The Gantt chart gives a relationship among different activities in a production process in terms
of their completion time. However, a Gantt chart does not provide an optimal sequence of jobs.
Many jobs in industry and elsewhere require completing a collection of tasks while satisfying
temporal and resource constraints. Temporal constraints say that some tasks have to be finished
before others can be started; resource constraints say that two tasks requiring the same resource
cannot be done simultaneously (e.g., the same machine cannot do two tasks at once). The objective
is to create a schedule specifying when each task is to begin and what resources it will use that
satisfy all the constraints while taking as little overall time as possible. This is the job-shop
scheduling problem.
In its general form, there is probably no efficient procedure for exactly finding shortest schedules
for such problems. However, by giving the scheduling tools some flexibility and guidance, it is
possible to produce a schedule that best uses the existing capacity. We will discuss some
algorithms in the following paragraphs. It should be kept in mind that these algorithms that are
applicable to job shops are also applicable to all flow shops that have similar characteristics.
To identify the performance measures, we will introduce some new measures, makespan and
utilization.

Did u know? What is Makespan?
The total amount of time required to complete a group of jobs is called makespan. This is
the sum total of the flow time for individual jobs.
Utilization: The per cent of work time productively spent by a machine or worker is called
utilization. Utilization for more than one machine or worker can be calculated by adding the
productive work times of all machines or workers and dividing by the total work time they are
available.
Makespan = Time of completion of last job – Starting time of first job

Utilization = Productive work time/ Total work time available
These performance measures are often interrelated.

Example: In a job shop, minimizing the mean job flow time tends to reduce work-in-
process inventory and increase utilization. In a flow shop, minimizing the makespan for a
group of jobs tends to increase facility utilization. An understanding of the interactions of job
flow time, makespan, past due, WIP inventory, total inventory, and utilization can make
scheduling easier.

Scheduling of ‘n’ Jobs on 1 Machine (n/1 Scheduling)

This type of scheduling problem is called the (N/1) scheduling problem. When many jobs are
waiting before an operational facility, we must have some heuristic or rule to decide the priority
while sequencing. Generally, this type of scheduling is done using simple scheduling procedures.
For scheduling simple jobs, some of the basic procedures that are used are First Come First
Served (FCFS), Shortest Production Time (SPT), Due Date (D Date), Last Come First Served
(LCFS), Random, and Slack Time Remaining (STR) rules.

288 LOVELY PROFESSIONAL UNIVERSITY