Production Scheduling Approaches
Read these sections, which highlight key problems in production scheduling. How can job sequencing and priority rules help to alleviate the key problems? Can you identify the different rules that affect job sequencing and priority rules in operations management?
3. Representation of scheduling instances
The possible representation of a JS problem could be done through a Gantt chart or through a Network representation.
Gantt created innovative charts for visualizing planned and actual production. According to Cox et al., a Gantt chart is, the earliest and best known type of control chart especially designed to show graphically the relationship between planned performance and actual performance". Gantt designed his charts so that foremen or other supervisors could quickly know whether production was on schedule, ahead of schedule or behind schedule. A Gantt chart, or bar chart as it is usually named, measures activities by the amount of time needed to complete them and use the space on the chart to represent the amount of the activity that should have been done in that time.
A Network representation was first introduced by Roy and Sussman. The representation is based on "disjunctive graph model". This representation starts from the concept that a feasible and optimal solution of JSP can originate from a permutation of task's order. Tasks are defined in a network representation through a probabilistic model, observing the precedence constraints, characterized in a machine occupation matrix M and considering the processing time of each tasks, defined in a time occupation matrix T.
JS processes are mathematically described as disjunctive graph G = (V, C, E). The descriptions and notations as follow are due to Adams et. al., where:
- V is a set of nodes representing tasks of jobs. Two additional dummy tasks are to be considered: a source(0) node and a sink(*) node which stand respectively for the Source (S) task τ0= 0, necessary to specify which job will be scheduled first, and an end fixed sink where schedule ends (T) τ*= 0;
- C is the set of conjunctive arcs or direct arcs that connect two consecutive tasks belonging to the same job chain. These represent technological sequences of machines for each job;
- E=⋃mr=1Dr⋃r=1mDr, where Dr is a set of disjunctive arcs or not-direct arcs representing pair of operations that must be performed on the same machine Mr.
Each job-tasks pair (i,j) is to be processed on a specified machine M(i,j) for T(i,j) time units, so each node of graph is weighted with j operation's processing time. In this representation all nodes are weighted with exception of source and sink node. This procedure makes always available feasible schedules which don't violate hard constraints
Hard constraints are physical ones, while soft constraints are generally those related to human factor e.g., relaxation, fatigue etc…
A graph representation of a simple instance of JSP, consisting of 9 operations partitioned into 3 jobs and 3 machines, is presented in fig. 1. Here the nodes correspond to operations numbered with consecutive ordinal values adding two fictitious additional ones:S = "source node" and T = "sink node". The processing time for each operation is the weighted value τij attached to the corresponding node,v∈Vv∈V, and for the special nodes, τ0 = τ*= 0.
Let sv be the starting time of an operation to a node v. By using the disjunctive graph notation, the JSPP can be formulated as a mathematical programming model as follows:
Minimize s* subject to:
Figure 1.
Disjunctive graph representation. There are disjunctive arcs between every pair of tasks that has to be processed on the same machine (dashed lines) and conjunctive arcs between every pair of tasks that are in the same job (dotted lines). Omitting processing time, the problem specification is
,
,
Job notation is used.
s* is equal to the completion time of the last operation of the schedule, which is therefore equal to Cmax. The first inequality ensures that when there is a conjunctive arc from a node v to a node w, w must wait of least τv time after v is started, so that the predefined technological constraints about sequence of machines for each job is not violated. The second condition ensures time to start continuities. The third condition affirms that, when there is a disjunctive arc between a node v and a node w, one has to select either v to be processed prior to w (and w waits for at least τv time period) or the other way around, this avoids overlap in time due to contemporaneous operations on the same machine.In order to obtain a scheduling solution and to evaluate makespan, we have to collect all feasible permutations of tasks to transform the undirected arcs in directed ones in such a way that there are no cycles.
The total number of nodes, fixed by taking
into account the total number of tasks |O|, is properly the total number
of operations with more two fictitious ones. While the total number of arcs, in
job notation, is fixed considering the number of tasks and jobs of instance:
E6
The number of arcs defines the possible combination paths. Each path from source to sink is a candidate solution for JSSP. The routing graph is reported in figure 2:
Figure 2.
Problem routing representation.