52 research outputs found
Train Scheduling on a Unidirectional Path
No full textWe formulate what might be the simplest train scheduling problem considered in the literature and show it to be NP-hard. We also give a log-factor randomised algorithm for it. In our problem we have a unidirectional train track with equidistant stations, each station initially having at most one train. In addition, there can be at most one train poised to enter each station. The trains must move to their destinations subject to the constraint that at every time instant there can be at most one train at each station and on the track between stations. The goal is to minimise the maximum delay of any train. Our problem can also be interpreted as a packet routing problem, and our work strengthens the hardness results from that literature
Complexity, bounds and dynamic programming algorithms for single track train scheduling
No full textIn this work we consider the single track train scheduling problem. The problem consists of scheduling a set of trains from opposite sides along a single track. The track has intermediate stations and the trains are only allowed to pass each other at those stations. Traversal times of the trains on the blocks between the stations only depend on the block lengths but not on the train. This problem is a special case of minimizing the makespan in job shop scheduling with two counter routes and no preemption. We develop a lower bound on the makespan of the train scheduling problem which provides us with an easy solution method in some special cases. Additionally, we prove that for a fixed number of blocks the problem can be solved in pseudo-polynomial time
Tight bounds on parallel list marking
No full textn)-PRAM, when only the location of the head of the list is initially known. Under the assumption that memory cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish an OHgr (min{ell, n/p}) randomized lower bound for ell-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. In the case where list cells are tagged in a way that differentiates them from other cells, we establish a tight theta (min {ell,ell/p + radic(n/p) log n }) bound for randomized algorithms
Scheduling Loosely Connected Task Graphs
No full textWe present a polynomial time algorithm for precedence constrained scheduling problems in which the task graph can be partitioned into large disjoint parts by removing edges with high float, where the float of an edge is defined as the difference between the length of the longest path in the graph and the length of the longest path containing the edge. Our algorithm guarantees schedules within a factor 1:875 of the optimal independent of the number of processors. The best known factor for this problem and in general is 2 \Gamma , where p is the number of processors, due to Coffman-Graham. Our algorithm is unusual and considerably different from that of Coffman-Graham and other algorithms in the literature
- …
