Pareto Boundary Based Multicriteria Scheduling

Since production scheduling is of great importance to manufacturing industries, the past six decades has witnessed numerous researches on this area. However, there is an obvious gap between academic research and manufacturing practice. Researchers usually take only one criterion into consideration while the practical manufacturing usually involves several criteria.Nowadays, multi-criteria scheduling is attracting increasing attention and the solving methodologies could be divided into three categories: priori, interactive and posteriori. This dissertation involves posteriori and interactive algorithms. Firstly, a self-organizing feature map based algorithm is proposed to acquire the Pareto boundary. Then, multi-criteria decision aids (MCDA) are applied in order to help the decision makers make the proper decision. In addition, to tackle some large-scale multi-criteria scheduling problems, an interactive algorithm based on outranking relation is also presented.In a nutshell, this dissertation comprises three parts:A new method is presented to generate approximate Pareto boundaries. First, Lagrange relaxation algorithm is applied to obtain several Pareto optima which are exploited to divide the search space into domains. Then, for each domain, two self-organizing feature map neural networks run simultaneously to explore the remaining Pareto optima.For the clustered Pareto boundaries, the k-mean algorithm is firstly applied to prune the Pareto boundary so that a much smaller Pareto set is achieved. Then PROMETHEE is used to handle the multi-criteria decision problems. For the dense type, an interactive algorithm is proposed. This"divide and conquer"approach enable the decision makers to avoid the decision making task on the large and cumbersome Pareto boundary.An interactive algorithm based on outranking relation is presented to addressing large scale multi-criteria scheduling problems. In each iteration, only a small part of Pareto boundary is generated according to decision maker's preference. The decision maker can then choose to change expectation point, to adjust base point or to alter preference information. This method is obviously time-saving since it doesn't require finding the whole Pareto boundary.