Some combinatorial optimization problems on radio network communication and machine scheduling.

摘要

The combinatorial optimization problems coming from two areas are studied in this dissertation: network communication and machine scheduling.;In the network communication area, the complexity of distributed broadcasting and distributed gossiping is studied in the setting of random networks. Two different models are considered: one is random geometric networks, the main model used to study properties of sensor and ad-hoc networks, where n points are randomly placed in a unit square and two points are connected by an edge if they are at most a certain fixed distance r from each other. The other model is the so-called line-of-sight networks, a new network model introduced recently by Frieze et al. (SODA'07). The nodes in this model are randomly placed (with probability p) on an n x n grid and a node can communicate with all the nodes that are in at most a certain fixed distance r and which are in the same row or column. It can be shown that in many scenarios of both models, the random structure of these networks makes it possible to perform distributed gossiping in asymptotically optimal time O(D), where D is the diameter of the network. The simulation results show that most algorithms especially the randomized algorithm works very fast in practice.;In the scheduling area, the first problem is online scheduling a set of equal processing time tasks with precedence constraints so as to minimize the makespan. It can be shown that Hu's algorithm yields an asymptotic competitive ratio of 3/2 for intree precedence constraints and an asymptotic competitive ratio of 1 for outtree precedences, and Coffman-Graham algorithm yields an asymptotic competitive ratio of 1 for arbitrary precedence constraints and two machines.;The second scheduling problem is the integrated production and delivery scheduling with disjoint windows. In this problem, each job is associated with a time window, and a profit. A job must be finished within its time window to get the profit. The objective is to pick a set of jobs and schedule them to get the maximum total profit. For a single machine and unit profit, an optimal algorithm is proposed. For a single machine and arbitrary profit, a fully polynomial time approximation scheme (FPTAS) is proposed. These algorithms can be extended to multiple machines with approximation ratio less than e/(e - 1).;The third scheduling problem studied in this dissertation is the preemptive scheduling algorithms with nested and inclusive processing set restrictions. The objective is to minimize the makespan of the schedule. It can be shown that there is no optimal online algorithm even for the case of inclusive processing set. Then a linear time optimal algorithm is given for the case of nested processing set, where all jobs are available for processing at time t = 0. A more complicated algorithm with running time O( n log n) is given that produces not only optimal but also maximal schedules. When jobs have different release times, an optimal algorithm is given for the nested case and a faster optimal algorithm is given for the inclusive processing set case.