A graph environment must be explored by a collection of mobile robots. Some of the robots, a priori unknown, may turn out to be unreliable. The graph is weighted and each node is assigned a deadline. The exploration is successful if each node of the graph is visited before its deadline by a reliable robot. The edge weight corresponds to the time needed by a robot to traverse the edge. Given the number of robots which may crash, is it possible to design an algorithm, which will always guarantee the exploration, independently of the choice of the subset of unreliable robots by the adversary? We find the optimal time, during which the graph may be explored. Our approach permits to find the maximal number of robots, which may turn out to be unreliable, and the graph is still guaranteed to be explored. We concentrate on line graphs and rings, for which we give positive results. We start with the case of the collections involving only reliable robots. We give algorithms finding optimal times needed for exploration when the robots are assigned to fixed initial positions as well as when such starting positions may be determined by the algorithm. We extend our consideration to the case when some number of robots may be unreliable. Our most surprising result is that solving the line exploration problem with robots at given positions, which may involve crash-faulty ones, is NP-hard. The same problem has polynomial solutions for a ring and for the case when the initial robots' positions on the line are arbitrary. The exploration problem is shown to be NP-hard for star graphs, even when the team consists of only two reliable robots.
A scheduling problem considered by the research community concerns @math jobs, each to be processed by a single machine, subject to arbitrary given precedence constraints; associated with each job @math is a known processing time @math and a monotone nondecreasing cost function @math , giving the cost that is incurred by the completion of that job at time @math . @cite_19 gives an efficient computational procedure for the problem of finding a sequence which will minimize the maximum of the incurred costs. Further, @cite_19 also studies a class of time-constrained vehicle routing and scheduling problems that may be encountered in several transportation distribution environments. In the single-vehicle scheduling problem with time window constraints, a vehicle has to visit a set of sites on a graph, and each site must be visited after its ready time but no later than its deadline. @cite_16 studies the problem of minimizing the total time taken to visit all sites. @cite_13 considers the problem of determining whether there exists a schedule on two identical processors that executes each task in the time interval between its start-time and deadline and presents an @math algorithm that constructs such a schedule whenever one exists.
@cite_19 @cite_16 @cite_13
2115299891 2042251310 2001364911
Suppose n jobs are each to be processed by a single machine, subject to arbitrary given precedence constraints. Associated with each job j is a known processing time aj, and a monotone nondecreasing cost function cjt, giving the cost that is incurred by the completion of that job at time t. The problem is to find a sequence which will minimize the maximum of the incurred costs. An efficient computational procedure is given for this problem, generalizing and simplifying previous results of the present author and J. M. Moore. In the single-vehicle scheduling problem with time window constraints, a vehicle has to visit a set of sites on a graph, and each site must be visited after its ready time but no later than its deadline. The goal is to minimize the total time taken to visit all sites. We prove the conjecture proposed by : if the topological graph is a straight line, the problems are NP-hard for both part and tour version. In addition, we give an O(n2) algorithm to solve a special case where all n sites have a common ready time. This algorithm illustrates a duality relationship between the vehicle scheduling problems with arbitrary ready times and that with arbitrary deadlines on a straight line. Copyright © 1999 John Wiley & Sons, Ltd. Given a set @math of tasks, each @math having execution time 1, an integer start-time @math and a deadline @math , along with precedence constraints among the tasks, we examine the problem of determining whether there exists a schedule on two identical processors that executes each task in the time interval between its start-time and deadline. We present an @math algorithm that constructs such a schedule whenever one exists. The algorithm may also be used in a binary search mode to find the shortest such schedule or to find a schedule that minimizes maximum “tardiness”. A number of natural extensions of this problem are seen to be @math complete and hence probably intractable.