Search

So many scheduling problems arise in railway industries. One of the typical scheduling problems is Crew Scheduling Problem. Much attention has been paid to this problem by a lot of researchers, but many studies have not been done to the problems in railway industries in Japan. In this paper, we consider a railway crew scheduling problem in Japan. The problem can be formulated into Set Covering Problem (SCP). In SCP, a row corresponds to a trip representing a minimal task and a column corresponds to a pairing representing a sequence of trips performed by a certain crew. Many algorithms have been developed and proposed for it. On the other hand, in practical use, it is important to investigate how these algorithms behave and work on a certain problem. Therefore, we focus on Wedelin's algorithm, which is based on Lagrange relaxation and is known as one of the high performance algorithms for SCP, and mainly examine the basic idea of this algorithm. Furthermore, we show effectiveness of this procedure through computational experiments on instances from Japanese railway.

This paper describes the results of a computational study using a particular enumeration procedure, called a backtrack algorithm, to find the lowest order of radio-frequency intermodulation. The average lowest order and its standard deviation, the average computer time and its standard deviation, along with other relevent statistics are obtained for a series of randomly generated problems with sets of five to 75 threat or source frequencies. Other parameters, such as the guard band, the maximum number of concurrent threats, and the size of the frequency band on the lowest order of intermodulation are varied during the computations. Statistics for these computer runs, along with those relating to terminating the algorithm when the lowest "acceptable" order is reached, are presented in some detail. Brief conclusions follow a listing of the results.

This paper discusses the problem of finding an interferencefree frequency assignment in a large communication system (e. g., in a large Naval fleet). In particular, the problem scenario, and the two algorithms, one an optimization procedure, and the second a heuristic technique, are discussed. The optimization algorithm is of the enumerative type and, in scenarios with a large communication system, may not terminate within a reasonable amount of computer time. To overcome this difficulty, an interactive heuristic-based software system is described which can be used by an astute decision maker to obtain a usable assignment relatively quickly.