Abstract
Optimization is a process of decision making which aims to finding the best alternative in order to achieve the goals as concerned. Regarding the kinds of variables, relations and the performance criterion, optimization problems are manifold. In this dissertation, we consider two kinds of optimization problems motivated from a case of Master Production Scheduling (MPS), namely optimization in permutation problems (in short, permutation optimization (PO)) and optimization in fuzzy linear programs (in short, fuzzy linear optimization (FLO)). Both optimization problems are of significance in application and in theorem. As optimization approaches, this study is meant to investigate the model structures and algorithms for PO, and for FLO. Both developments are outlined below: (1) Permutation property has been recognized as a common but challenging feature in combinatorial problems. We express a general form of PO, which is capable of presenting the structures and complexity of various permutation problems. Because of their complexity, recent research has turned to genetic algorithms for solving such problems. Although genetic algorithms have been proven to facilitate the entire space search, they lack in fine-tuning capability for obtaining the global optimum. Therefore, in this study a hybrid genetic algorithm is developed by integrating both evolutional and neighborhood searches for PO. On the analysis of such hybridization, the pros and cons compensation between genetic algorithm and neighborhood search are particularly addressed. (2) In real-world applications, certain kinds of uncertainty are not stochastic. For intrinsic uncertainty, the concept of fuzzy sets was suggested. With these fuzzy input data that are presented by subjective membership functions, fuzzy linear programming is to enhance the capability of linear programs by individual’s perception. Although a number of researches have focused on the development of optimization in fuzzy linear programs, how to explicitly present one’s preference has never been addressed, neither the overall tolerance, and solution procedure. In this study, we developed an FLO model based on preference approach, which is capable of incorporating one’s optimistic or pessimistic attitude as well as admitting tolerances of all coefficients. Because of its complex with a non-linear model, the time consumed in finding a compromise solution is also a core issue for the development of FLO. However, by investigating its inherited linear character, we elaborate a basis-based algorithm for solving the proposed FLO problem. The results of this study have shown to be effectively applicable for the case of MPS. Experimental results of the MPS problem indicate that the hybrid genetic algorithm outperforms the other tested methods, in particular for larger scaled problems. Moreover, this implementation verifies the need of applying our proposed preference approach for the fuzzy optimization, and signifies the superiority of the proposed basis-based algorithm comparing to the Dinkelbach-type-2 algorithm and the bisection procedure.