Combination Of Shop Scheduling Problems And Shortest Path Problems

We study several combinatorial optimization problems which are obtained by com-bining the three classical shop scheduling problems, and the shortest path problem re-spectively. The objective of the obtained problem is to select a subset of jobs constitutesa feasible solution to the shortest path problem, and to execute the selected jobs on a shopmachine to minimize the makespan.In this thesis, we first consider the computational complexities of these problems.The first result is that these combination problems are NP hard even if the number ofmachines is two. Second, we prove that if the number of machines is an input of theinstance, no polynomial approximation algorithm can achieve a worst-case ratio less than2unless P=NP. In particular, we propose several algorithms for these problems accord-ing to their diferent structures and features, and analyze both the time complexities andapproximation performances. Finally, we discuss about extending the previous results ofcombining shop scheduling problem with the minimum spanning tree problem, or cover-ing problem. We argue that all the previous results can be extended to the combinationproblem of shop scheduling and those two problems respectively.The main contributions of this thesis are described as follows:1. By combining the shop scheduling problem and shortest path (minimum span-ning tree, covering) problem, we propose several novel combination problems. Weprove the computational complexities of those problems, and propose several ap-proximation algorithms for them.2. For the special feature of shop scheduling problem, we propose a more generalizedcovering problem, and apply it to define the combination of those two problems.This is a more general definition for the combination of optimization problems.3. For those combination problems, according to the particular features of the resultsreturned by the known shop scheduling algorithms, we propose several approxima-tion algorithms based on the idea of repeatedly implementing the known algorithmsand modifying the values of the weights. We extend the application of this idea.