Introduction

In manufacturing and assembly situations there is a practical limit to the resources available to the operator. For example manpower may be limited, there may only be a certain number of machines available and the machines may be expensive to operate either because of power consumption or manpower requirements. A particular process anticipated by a manufacturer will consist of a number of jobs which must be carried out in a certain order for successful completion.

To make matters more complex there is the problem of outside suppliers, will their parts arrive on time? Will the parts delivered fulfil their purpose? The scheduler or project manager must take all these things into account when planning a production process. Their job is to ensure that the process is brought to a successful completion, with a minimum of time and cost. In other words their job is to optimise the schedule.

... objective is ... a schedule which minimises the total process time

A typical optimisation objective is to find a schedule which minimises the total process time. This is often referred to as the makespan. Needless to say this is easier said than done since for any schedule above the trivial, the potential combinations rise exponentially as the complexity increases.

Basic Jobshop scheduling

The classic jobshop (Bagchi 99) distinguishes itself from other flowshop problems in that the operations are not carried out unidirectionally, i.e. there is no set machine which carries out the first operation of a job and no set machine which terminates the job.

For a particular situation there will be n jobs carried out on m machines. Each job consists of o operations. Each of the operations associated with a job must be carried out in sequence i.e. o_i < o_i+1 and each operation is associated with one or more machines. An operation associated with a particular job and machine will have an estimated duration.

Jobshop problem (JSP)

Formally the basic jobshop scheduling problem (JSP) can be described by an integer programming model (Greenberg 68, Baker 74, Cheng 96), assuming the following notation:

m

Number of machines

n

Number of jobs

t_ijk

Processing time of operation j of job i on machine k

x_ik

Completion time of job i on machine k

Y_ipk

Indicator variable for job precedence

k_i

Machine on which last operation of job i is scheduled

H

A large positive number

Indicator variables are used to specify operation sequences. A number of inequalities are also required to represent the precedence constraints, for example (Figure 1):

To ensure that operation j-1 of job i on machine h precedes operation j of job i on machine k, then it is necessary to have:

x_ik-x_ih ≥ t_ijk 1 ≤ k,h ≤ m, 1 ≤ i ≤ n

Similarly when job p precedes job i on machine k, it is necessary to ensure that operation p,q,k is completed prior to commencement of operation i,j,k, (see Figure 2).

Which can be expressed as:

x_ik-x_pk ≥ t_ijk 1 ≤ k ≤ m, 1 ≤ i,p ≤ n

Introducing the indicator variable such that:

Y_pik = 1, if job p precedes job i on machine k
Y_pik = 0, otherwise

The constraint then becomes:

x_ik-x_pk ≥ t_ijk + H(1-Y_pik) 1 ≤ k ≤ m, 1 ≤ i,p ≤ n

Which only evaluates when job p precedes job i. Similarly if job i precedes job p the constraint can be described:

x_pk-x_ik ≥ t_ijk + H(Y_pik) 1 ≤ k ≤ m, 1 ≤ i,p ≤ n

Which will only evaluate when job i precedes job p. This leads to a generalised expression for the minimisation of the makespan:

Minimise: ∑ x_ki

Subject to:

xik-xpk ≥ tijk	∀(i,j-1,h)∈(i,j,k)
xik-xpk ≥ tijk + H(1-Ypik)	1 ≤ k ≤ m, 1 ≤ i,p ≤ n
xpk-xik ≥ tijk + H(Ypik)	1 ≤ k ≤ m, 1 ≤ i,p ≤ n
xik≥0, Ypik=(0,1)

This is only of interest in that it shows the number of variables that are required to solve JSPs by this method. The number of decision variables for this formulation is given by mn(n+1)/2 (Bagchi 99). For a 20 job, 4 machine problem this gives 1600 constraints and 1680 decision variables.

A more complex Jobshop schedule

So far we have described a basic jobshop schedule, unfortunately this is rarely sufficient to satisfy practical applications. It is often the case that dependencies exist within a schedule, i.e. job and time dependencies.

Also a particular operation may be performed on more than one machine with varying capabilities, for example a particular operation could be carried out on a drilling machine with 100% efficiency, or carried out on a milling machine with only 30% efficiency, either option may be viable.

These factors while adding greatly to the complexity of the problem nevertheless provide a more accurate picture of a real machine shop. The model described here (Todd 97) encompasses many of these factors. These can be summarised by the following sets of rules which may be applied to make scheduling problems more practical.

• There are k machines and n different jobs encompassing the jobshop
• Each job is composed of a set of m (or less) stages required for completion
• Each stage requires a specific operation
• Each stage has a standard processing time, assumed to be 100%
• Each stage must be carried out in a specific order
• A job can visit a machine one or more times depending upon operations
• There are interdependencies between different jobs, i.e. a job cannot start until another is completed
• Operations cannot be interrupted
• Each machine can only process one job at a time (functional limitation)
• Release times and due dates are specified
• Machines can perform several operations (i.e. are multi-functional)
• Machines perform different operations with differing efficiencies
• Machine maintenance times may be specified
• Machine set-up times for operations can be specified
• Due date penalties can be specified
• Multiple scheduling criteria can be optimised

These rules can be facilitated by a number of data tables, which describe the scheduling constraints. Because of the flexibility of these rules, these can be easily implemented when scheduling practical jobshops.

Schedule criteria

In a practical situation, minimising the makespan may not be sufficient, for many industrial situations a number of other factors may be relevant. When this is done, this makes the problem a multiple criteria decision making problem, with the makespan constituting just one possible criterion.

Considering this further, a number of factors may be determined, which are of potential interest to the scheduler. The most immediate ones are penalty deadlines and average job times.

Penalty deadlines

In a practical situation a scheduler will often be able to specify a deadline for when a particular job must be finished. The penalties associated with this may be contractual costs incurred by customers, or simply a knock-on effect with other processes being delayed further down the line. In either case it is of interest to the scheduler that the possibilities of this happening is minimised.

Average job times

Average job times are of specific interest since these are directly related to the time a machine is run. This may be relevant due to the cost of the power supply or wear down of parts and labour costs and the operator has an interest in minimising these factors.

The jobshop model discussed here is not comprehensive, however it is sufficiently flexible that other criteria can be simply included into it.

A list of potential criteria are shown in the following list (Bagchi 99).

Criteria	Objectives
Budget	Cost minimisation
Production	Production output maximisation
	Minimisation of makespan
	Resource utilisation
Quality Control	Maximisation of product quality
	Minimisation of rework
Personnel	Minimisation of personnel utilisation
Marketing	Continuity of supply to customers

Based on this discussion software can easily be designed to create schedules. Typically this can measure and compare:

• makespan with penalty values, and
• makespan with average job times.

By using trade-offs like these, optimisation techniques such as Genetic Algorithms can be used to find the most efficient schedules for a given Jobshop. These techniques become much more interesting when imprecise timings are introduced into the methodology and this will be the subject of a future research highlight.

Author: John Dalton

Contact: john.dalton@ncl.ac.uk

References

1. Bagchi, T.P., "Multiobjective Scheduling by Genetic Algorithms", Kluwer Academic Publishers, 1999.
2. Greenberg, H., "A Branch-and-Bound Solution to the General Scheduling Problem", Operations Research, 1968.
3. Baker, K., "Introduction to Sequencing and Scheduling", John Wiley & Sons, 1974.
4. Cheng, R.M.; Gen, M.; Tsujimura, Y., "A Tutorial Survey of Jobshop Scheduling Problems using Genetic Algorithm: Pt I Representation", International Journal of Computers and Industrial Engineering, 1996.
5. Todd, D., "Multiple Criteria Genetic Algorithms in Engineering Design and Operation", PhD Thesis, Engineering Design Centre, University of Newcastle Upon Tyne, October 1997.