Bicriteria scheduling problem on parallel machine

Abstract

This paper shows the parallel machine

scheduling problem with sequence dependent

set up times. The purpose is to schedule the

jobs to minimize the weighted sum of

average completion time and average

tardiness of the jobs. The aim is to maintain a

good service with minimum work in process.

This research analyzes the behaviour of six

simple heuristics easily to implement for

practitioners which are the combination of

three simple procedures to obtain an initial

solution and two improvement procedures;

one that acts on a neighbourhood formed

from the sequences for each machine and

another that acts on the neighbourhood

established from the sequences in each

machine. The results show that the second

improvement procedure, which is closer to the

matter of the problem, leads to better results.

According to this result, the performance of

the initial procedures, when the weighted of

the two criteria are varied, has been studied.

The results of the test show that, for more

balanced criteria, the initial procedures which

consider those criteria lead to better results.