Mathematical modelling of multi-objective job shop scheduling with dependent setups and re-entrant operations

For the last thirty years, in job shop scheduling, the setup times of operations have been either ignored or combined with their corresponding processing times, independent setups, to simplify the work of model construction. However, in practice, the setup times of an operation are usually considered be sequence-dependent. Moreover, the performance of a scheduling system is not evaluated to satisfy a single objective, but to obtain a trade-off solution regarding multiple objectives. Therefore, this paper investigates job shop scheduling problems with re-entrant operations where the setup times, which vary according to the preceding operation which is processed on the same machine, and which can be separated from their corresponding processing times, cannot be omitted. Three practical performance measures – minimum total job flow time, minimum total job tardiness and minimum machine idle time – are considered. An integer programming model is first developed to optimise each single objective and an acceptable trade-off schedule, which makes use of a multiple-decision-making technique, the global criterion method, is obtained by evaluating three objectives simultaneously .