388
Figure 3 below illustrates how five tasks have to go through the same route (green blue
pink yellow red) but tasks 2 and 3 skip the blue activity. Also, activity green can process
up to 2 tasks at time, which means two parallel machines can perform green.
Blue, yellow, and red activities also have 2 parallel machines. Pink, only one.
Other modifications considered:
• instead of the commonly applied makespan, objective function was changed to maximize
metal production within a given period, in this case, the duration of the plan (e.g., 15 or
30 days). It is considered that, beyond this point in time, we do not have enough tasks or
information to schedule the tasks in a complete plan.
• Precedences between tasks activities are allowed and have to be listed. Thus, we can explicitly state that task 2 activity 1 happens only after task 3 activity 4.
2.1 Mathematical model
To model and solve this problem a Mixed Integer Linear Programming (MIP) model (Wolsey,
1998) is proposed. The model can be fully described by its inputs, variables (which will also be
outputs), objective function and constraints; the latter two described by linear equations.
2.1.1 Inputs
• F timeframe within optimization interests;
• m j array with the number of parallel machines for each activity j;
Figure 2. Example of a flow shop with 5 tasks and 5 machines.
Figure 3. Example of the flow shop scheduling problem with parallel machines (approach used for the
underground mine short-term schedule problem).
TASK 1 I
I
TASK2
D
TASK3
D l
I
I
-
TASK4
D D l I D I
TASKS
D
D D D I
TASK 1 L - -
1
- - - - - - ' - - - - - - - - '
TASK 2
TASK 3
' - - - - - - - - ' - - --' --------TASK4
TASK 5
D L__
l . . . . t . _________---- 1
Figure 3 below illustrates how five tasks have to go through the same route (green blue
pink yellow red) but tasks 2 and 3 skip the blue activity. Also, activity green can process
up to 2 tasks at time, which means two parallel machines can perform green.
Blue, yellow, and red activities also have 2 parallel machines. Pink, only one.
Other modifications considered:
• instead of the commonly applied makespan, objective function was changed to maximize
metal production within a given period, in this case, the duration of the plan (e.g., 15 or
30 days). It is considered that, beyond this point in time, we do not have enough tasks or
information to schedule the tasks in a complete plan.
• Precedences between tasks activities are allowed and have to be listed. Thus, we can explicitly state that task 2 activity 1 happens only after task 3 activity 4.
2.1 Mathematical model
To model and solve this problem a Mixed Integer Linear Programming (MIP) model (Wolsey,
1998) is proposed. The model can be fully described by its inputs, variables (which will also be
outputs), objective function and constraints; the latter two described by linear equations.
2.1.1 Inputs
• F timeframe within optimization interests;
• m j array with the number of parallel machines for each activity j;
Figure 2. Example of a flow shop with 5 tasks and 5 machines.
Figure 3. Example of the flow shop scheduling problem with parallel machines (approach used for the
underground mine short-term schedule problem).
TASK 1 I
I
TASK2
D
TASK3
D l
I
I
-
TASK4
D D l I D I
TASKS
D
D D D I
TASK 1 L - -
1
- - - - - - ' - - - - - - - - '
TASK 2
TASK 3
' - - - - - - - - ' - - --' --------TASK4
TASK 5
D L__
l . . . . t . _________---- 1