Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Algorithms And Complexity Analyses For Some Combinational Optimization Problems, Hairong Zhao
Algorithms And Complexity Analyses For Some Combinational Optimization Problems, Hairong Zhao
Dissertations
The main focus of this dissertation is on classical combinatorial optimization problems in two important areas: scheduling and network design.
In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. Each slave task has a dedicated slave machine. All the preprocessing and postprocessing tasks share a single master machine or the same set of master machines. A job may …
Order Scheduling In Dedicated And Flexible Machine Environments, Haibing Li
Order Scheduling In Dedicated And Flexible Machine Environments, Haibing Li
Dissertations
Order scheduling models are relatively new in the field of scheduling. Consider a facility with m parallel machines that can process k different products (job types). Each machine can process a given subset of different product types. There are n orders from n different clients. Each order requests specific quantities of the various different products that can be produced concurrently on their given subsets of machines; it may have a release date, a weight and a due date. Preemptions may be allowed. An order can not be shipped until the processing of all the products for the order has been …
Approximation Algorithms For Variants Of The Traveling Salesman Problem, Ankur Gupta
Approximation Algorithms For Variants Of The Traveling Salesman Problem, Ankur Gupta
Theses
The traveling salesman problem, hereafter abbreviated and referred to as TSP, is a very well known NP-optimization problem and is one of the most widely researched problems in computer science. Classical TSP is one of the original NP - hard problems [1]. It is also known to be NP - hard to approximate within any factor and thus there is no approximation algorithm for TSP for general graphs, unless P = NP. However, given the added constraint that edges of the graph observe triangle inequality, it has been shown that it is possible achieve a good approximation to the optimal …