Multi-Objective Scheduling Problems Subjected to Special Process Constraint


The problem of parallel machine multi-objective scheduling subjected to special process constraint in the textile industries, as one of the most important combinational optimization problems, is different from other parallel machine scheduling problems in the following characteristics. On one hand, processing machines are non-identical; on the other hand, the sort of job processed on every machine can be restricted. Considering one of the multi-objective problems, either minimizing the maximum completion time among all the machines(makespan) or minimizing the total earliness/tardiness penalty of all the jobs has been cornerstone of most studies done so far. However, under special process constraint, taking them into account as a multi-objective problem has not been well studied. Therefore, in this paper, a multi-objective model based on them is presented and a new parallel genetic algorithm based on a vector group coding method is also proposed in order to effectively solve this model. The algorithm shows the following advantages: the coding method is simple and can effectively reflect the virtual scheduling policy, which can vividly reflect the numbers and sequences of these processed jobs on every machine, and then enables the individuals generated by crossover and mutation to satisfy process constraint. Numerical experiments show that it is efficient, and is better than the common genetic algorithm, and has the better parallel efficiency. A much better prospect of application can be optimistically expected.