Fast Generic Insertion Algorithms For Sequence Problems

Combinatorial optimization is one of most active subject of mathematical optimization which is related to operations research, algorithm theory, and computational complexity theory. Sequencing problems are among the most widely studied problems in combinatorial optimization which require the determination of a best order of performing a given set of operations.In this thesis we will discuss two kinds of sequencing problems: graph layout problems and scheduling problems. Because there is a strong relevance between these two kinds of problems and we even can use a disjunctive graph model to formulate a scheduling problem to a graph layout problem, we put these two problems in one thesis and discuss them together.Graph layout problems have a wide use in numerical analysis, computational biology, scheduling and so on. Scheduling problems play an important role in supply chain and production programming.For the graph layout problems, we will discuss linear arrangement problem on non-oriented trees, which is kind of minimum linear arrangement problem. The objective of this problem is to find a linear layout according to a non-oriented tree in such a way a certain objective function is optimal. In this part we will design and implement two inserting algorithms.For the scheduling problem, integrated production and transportation scheduling problems will be talked, which is a job shop scheduling problem with transportation and capacity constraints. This problem is aimed to find a transportation and production scheduling and try to minimize the makespan, which is the maximum of the completion times of all operations and transportation. In this part firstly a mathematical model for this problem will be proposed. Then according to this mathematical model, one algorithm and one criterion will be designed and implemented.