No description available.

Decision trees are one of the most commonly used tools in decision analysis, knowledge representation, machine learning, etc., for its simplicity and interpretability. We consider an extension of dynamic programming approach to process the whole set of decision trees for the given decision table which was previously only attainable by brute-force algorithms. We study decision tables with many-valued decisions (each row may contain multiple decisions) because they are more reasonable models of data in many cases. To address this problem in a broad sense, we consider not only decision trees but also inhibitory trees where terminal nodes are labeled with “̸= decision”. Inhibitory trees can sometimes describe more knowledge from datasets than decision trees. As for cost functions, we consider depth or average depth to minimize time complexity of trees, and the number of nodes or the number of the terminal, or nonterminal nodes to minimize the space complexity of trees. We investigate the multi-stage optimization of trees relative to some cost functions, and also the possibility to describe the whole set of strictly optimal trees. Furthermore, we study the bi-criteria optimization cost vs. cost and cost vs. uncertainty for decision trees, and cost vs. cost and cost vs. completeness for inhibitory trees. The most interesting application of the developed technique is the creation of multi-pruning and restricted multi-pruning approaches which are useful for knowledge representation and prediction. The experimental results show that decision trees constructed by these approaches can often outperform the decision trees constructed by the CART algorithm. Another application includes the comparison of 12 greedy heuristics for single- and bi-criteria optimization (cost vs. cost) of trees. We also study the three approaches (decision tables with many-valued decisions, decision tables with most common decisions, and decision tables with generalized decisions) to handle inconsistency of decision tables. We also analyze the time complexity of decision and inhibitory trees over arbitrary sets of attributes represented by information systems in the frameworks of local (when we can use in trees only attributes from problem description) and global (when we can use in trees arbitrary attributes from the information system) approaches.

Cellular manufacturing, which is also referred to as group technology among researchers, has primarily been used as a means to increase productivity, efficiency and flexibility. Under group technology, similar jobs, which have similar shape, material, and processing operations are assigned to the same group. Moreover, dissimilar machines are assigned to the same cell to meet the processing requirements of jobs in a group or multiple groups. Group scheduling problems have been studied extensively in the past as implementation of group technology became more prevalent in industry. However, most of the work that has been done has focused on single-criterion optimization. A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this research. Cellular manufacturing and flow shop are two popular scenarios in industry. To mimic real industry practice, dynamic job releases and dynamic machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which satisfy the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two goals. Two different initial solution finding mechanisms are proposed, and a tabu-search based two-level search algorithm is developed to find near optimal solutions for the problem. An example problem is used to demonstrate the applicability of the search algorithm. A mathematical model is developed and implemented to evaluate the quality of the solutions obtained from the heuristics in small problem instances. Further, to uncover the difference in performance of initial solution finding mechanisms and heuristics, a detailed experimental design is performed. The results show that different heuristics have different performance in solving problems generated with different parameters. / Graduation date: 2012

This thesis is devoted to the development of extensions of dynamic programming to the study of decision trees. The considered extensions allow us to make multi-stage optimization of decision trees relative to a sequence of cost functions, to count the number of optimal trees, and to study relationships: cost vs cost and cost vs uncertainty for decision trees by construction of the set of Pareto-optimal points for the corresponding bi-criteria optimization problem. The applications include study of totally optimal (simultaneously optimal relative to a number of cost functions) decision trees for Boolean functions, improvement of bounds on complexity of decision trees for diagnosis of circuits, study of time and memory trade-off for corner point detection, study of decision rules derived from decision trees, creation of new procedure (multi-pruning) for construction of classifiers, and comparison of heuristics for decision tree construction. Part of these extensions (multi-stage optimization) was generalized to well-known combinatorial optimization problems: matrix chain multiplication, binary search trees, global sequence alignment, and optimal paths in directed graphs.

In cellular manufacturing systems, minimization of the completion time has a great impact on the production time, material flow, and productivity. An effective scheduling is crucial to attaining the advantages of cellular manufacturing systems. This dissertation attempts to solve the Flowshop Manufacturing Cell (cellular flowshop) Scheduling Problem with Sequence Dependent Setup Times (FMCSP with SDSTs) considering two performance measures: the total flow time as a mono objective, and the makespan and total flow time combined as a bi-criteria scheduling problem. The proposed problem is known to be the NP-hard problem because of its complexity. Several metaheuristic algorithms based on Genetic Algorithm (GA), Simulated Annealing (SA), and Particle Swarm Optimization (PSO) are developed for scheduling part families as well as jobs within each part family for FMCSP with SDSTs to minimize the total flow time. A local search method based on SA combined with PSO (named as PSO-SA) is proposed to enhance the intensification and improve the quality of the solution obtained by pure PSO. The effectiveness and efficiency of the proposed metaheuristics are evaluated based on the Relative Percentage Deviation (RPD) from its lower bound, and the robustness. Results indicate PSO-SA is performed similar to best available algorithms for small and medium size test problems. Yet, there is a very small deviation from best results for large problems. A Multi-objective Particle Swarm Optimization (MPSO) and a Multi-objective Simulated Annealing (MOSA) Algorithm are further proposed to solve the bi-criteria optimization problem to minimize the total flow time and makespan simultaneously. An improved PSO is combined with Threshold Acceptance (TA) algorithm to improve effectiveness of the proposed MPSO (named as IMPSO-TA) for the convergence of the obtained Pareto Front. The proposed algorithms are evaluated using several Quality Indicators (QI) measures for multiobjective optimization problems. The proposed algorithms can generate approximated Pareto Fronts in a reasonable CPU time. The proposed IMPSO-SA outperforms MOSA algorithm in terms of CPU time and minimizing the objective functions. / October 2015

No description available.