Search

To cope with growing passenger demand and to provide better services, increasing the number of trains is desired for certain lines. Maximum possible throughput of a line is often limited due to the limited number of platforms at the terminal, which was the case with two bullet-train lines originating from Tokyo. In these lines, there exists an intermediate station in the close vicinity of the terminal. This paper proposes a network-based optimization model to analyze the throughput of a line when turn-backs at the adjacent station are introduced to increase the line capacity.

We consider the allocation of a running time supplement to a railway timetable. Previously, Vekas et al. developed a stochastic programming model. In this paper, their optimization model is improved by adding bound constraints on the supplements. It is shown that the probability of delays decreases when using the proposed model. In addition, an effective L-shaped algorithm is presented.

Optimization of vehicle routes with delivery and pickup for a rental industry is considered. The company delivers to or pickups from customers rented products. Several types of products exist, and customers rent the specified number of products of the specific type. Time windows exist for delivery and pickup. There exist two sizes of vehicles, and their trips start from and end at depot and vehicles can make several trips during a day. Delivery must precede pickup on any trip of a vehicle. Capacity of vehicles depends on product type and also on how products are loaded on vehicles. Depending on demand quantity, split deliveries/pickups may be necessary. The company wants to minimize the total transportation cost. Based on the fact that the total number of distinct trips is rather small due to limited capacity of the vehicles, our solution strategy first enumerates all possible trips. Routes (i.e., collection of trips) are obtained by assigning trips to vehicles so that the total cost is minimized subject to constraints on demand, an upper limit on the number of trips per vehicle, and time compatibility of trips assigned to each vehicle. Since there exist many time compatibility constraints, the problem is first solved without them, we then check the compatibility and if necessary add compatibility constraints, and the problem is solved again until all routes become time compatible. Computational performance of the proposed solution approach is evaluated.

It is necessary for railway companies to construct daily schedules of assigning rolling stocks to utilization paths. A utilization path consists of a series of trains that a particular rolling stock performs in a day. A mixed integer programming model based on Lai et al. [1] is presented and is shown that straightforward applications of the model result in too much computational time and also inappropriate assignment schedules due to end effects. We show that the model can be modified to alleviate these difficulties, and also show that the repeated applications of the optimization model in the rolling horizon allow to generate a feasible assignment schedule for a longer period of time thus indicating the feasibility of the optimization approach.

The unit commitment problem is to determine the schedule of power generating units and the generating level of each unit. The decisions involve which units to commit at each time period and at what level to generate power to meet the electricity demand. We consider the heuristic column generation algorithm to solve this problem. Previous methods used the approach in which each column corresponds to the start–stop schedule and output level. Since power output is a continuous quantity, it takes time to generate the required columns efficiently. In our proposed approach, the problem to be solved is not a simple set partitioning problem, because the columns generated contain only a schedule specified by 0–1 value. It is shown that the proposed heuristic approach is effective to solve the problem.

In recent years, it has been difficult for manufactures and suppliers to forecast demand from a market for a given product precisely. Therefore, it has become important for them to cope with fluctuations in demand. From this viewpoint, the problem of planning or scheduling in production systems can be regarded as a mathematical problem with stochastic elements. However, in many previous studies, such problems are formulated without stochastic factors, treating stochastic elements as deterministic variables or parameters. Stochastic programming incorporates such factors into the mathematical formulation. In the present paper, we consider a multi-product, discrete, lotsizing and scheduling problem on parallel machines with stochastic demands. Under certain assumptions, this problem can be formulated as a stochastic integer programming problem. We attempt to solve this problem by a scenario aggregation method proposed by Rockafellar and Wets. The results from computational experiments suggest that our approach is able to solve large-scale problems, and that, under the condition of uncertainty, incorporating stochastic elements into the model gives better results than formulating the problem as a deterministic model.

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.

In this paper, we introduce a class of stochastic programming problem with fixed charge recourse in which a fixed cost is imposed if the value of the continuous recourse variable is strictly positive. The algorithm of a branch-and-cut method to solve the problem is developed by using the property of the expected recourse function. Then, the problem is applied to a power generating system. The numerical experiments show that the proposed algorithm is quite efficient. The mathematical programming model defined in this paper is quite useful for a variety of design and operational problems.

Daily route generation of home care staff is considered and a column generation heuristic is developed. Constraints considered include staff working hours, time window for each visit, means of transportation (bicycle/car), maximum allowable idle time between visits, patient/staff compatibility, among others. Since it is desired to generate compact routes in the geographically scattered area, the minimization of total travel time is used. Computational results based on real data will be presented. To further reduce CPU time, pre-processing of input data is performed to reduce the solution space by narrowing the time window of visits and by limiting candidate staff members who could be assigned to a specific visit. The pre-processing is performed by solving two small 0–1 programs. It is shown how the pre-processing cuts down the CPU time of the column generation algorithm.

We present a new control scheme for releasing parts into a flexible manufacturing system (FMS) that is based on incremental optimization. Our objective is to exploit the available routing flexibility of parts in an enhanced manner by viewing part release as an assignment problem using system status information. In particular, we propose an “intelligent” part release mechanism with some look-ahead and optimization features in order to allow for optimization-based “cooperation” of workcenters. The cooperative dispatching concept is implemented in an object-oriented computer simulation model, and experiments with a varying degree of average routing flexibility are performed. The experimental results are used for a statistical analysis of the benefits of cooperative dispatching versus the common approach of standard dispatching. Finally, we investigate the robustness of the presented FMS control scheme in the case of random machine breakdowns.

Score orienteering is a variant of the orienteering game where competitors start at a specified control point, visit as many control points as possible and thereby collect prizes, and return to the starting point within a prescribed amount of time. The competitor with the highest amount of prizes wins the game. In this paper, we propose the minimum directed 1-subtree problem as a new relaxation to this problem and develop two methods to improve its lower bound. We describe a cut and dual simplex method and a Lagrangian relaxation method, and construct an algorithm that combines these two methods in an appropriate way. Computational experiments are carried out to analyse the behavior of the proposed relaxation with respect to the characteristics of the test problems. Especially for large-scale instances, we find that the proposed relaxation is superior to the ordinary assignment relaxation.

We consider the allocation of a running time supplement to a railway timetable. Previously, Vekas et al. examined the optimal way to allocate the running time supplement. The uncertain disturbances in a railway were modeled using random variables. In their model, it was assumed that there was an upper limit to the total supplement, but its allocation was not restricted. In this paper, we suggest an improvement to the previous model and present a new stochastic programming model in which there is a constraint on the running time supplement allocated to each trip to minimize the expected delay. Then a solution algorithm to solve the problem is developed. In the previous model, allocation of the running time supplement was biased because it was not allocated to all trips. We balance the amounts of supplements for trips by adding upper and lower bounds. The fluctuations of the supplements for trips become small, and the probability of a delay decreases using our new model. Then the calculation times using the L-shaped algorithm and the former method solving a deterministic equivalent of large-scale problems are compared. It is shown that the large-scale problems can be solved effectively by using the L-shaped method.

It is commonly believed that the use of the assignment problem works well when one selects a relaxation problem within the framework of a branch and bound algorithm to solve an asymmetric traveling salesman problem (TS P) optimally. In this paper, we present asymmetric TSP instances found in real-life setting, and show that t.he above common belief is not necessarily appropriate. Based on the real-life example, a family of asymmetric TSP instances called SLOPE is considered, which are generated by deforming arc lengths of standard two-dimensional TSPs on a plane in a, specific manner. For this type of instances, we show that the assignmellt relaxation yields poor performance, and propose a minimum 1-arborescence relaxation similar to the minimum i-tree relaxation that has been successfullv applied to the symmetric TSPs. In order to make the algorithm more efficient, the propel' selection of Cc ro;t node and the detenninat,ion of Lagrange multipliers to increase the lower bounds are explored. Computational experiments with instances SLOPE and also with t.he real-life instance show that the proposed algorithm gives better computational performance than the algorithm with the assignment relax­ ation.

Two or more multiplicative congruential random-number generators with prime modulus combined by means of a method proposed by Wichmann and Hill (1982) yield a random-number generator equivalent to a multiplicative congruential random-number generator with modulus equal to the product of the moduli of the component multiplicative congruential generators. The period of a random-number sequence obtained by the Wichmann-Hill method is equal to the least common multiple of the periods of the combined sequences. One of the two purposes of this paper is to present a necessary and sufficient set of efficiently verifiable conditions for the period to be equal to its maximum, which is the maximum of the least common multiple. Each of the conditions is always satisfied or is more easily verifiable when the modulus of each of the component generators is a safe prime. The other purpose of this paper is to derive an efficiently evaluatable formula for serial correlations of the maximum-period sequences by the Wichmann-Hill method. The authors recommend (i) to make the modulus of each of the component generators a safe prime, and (ii) to chose the multipliers of the components so as to (a) maximize the period and (b) make the serial correlations small in absolute value.

Previous research on inventory distributions between local warehouses or retailers (bases) has focused separately on either of two types of stock transshipment policies: preventive lateral transshipments or emergency lateral transshipments. Each of these has its advantages and disadvantages, and combining these policies may well enable merchandisers to achieve higher service levels. Thus, the combined use of these policies is the focus of the present study. A stochastic programming problem is formulated with demand as a stochastic variable, and the policy of using both preventive and emergency lateral transshipment is examined for its effectiveness while solution methods are examined for their efficiency.

We present a general framework for a combined optimization/simulation approach where constraints to be satisfied are identified from results of simulation evaluation of the proposed system alternative, and then these constraints are added to the optimization model for re-optimization. The proposed cutting-plane-like procedure is iterative and terminates when an "optimal" solution of a mathematical program is obtained which passes all conditions of performance criteria set for simulation evaluation. A case of the real large-scale logistic system design is taken as an example, and the proposed approach is shown to work efficiently for the case, and looks promising for other problems, especially in the field of logistics and scheduling.

An efficient simulation/optimization approach is presented for finding a dynamic dispatching priority in a static job shop environment under the presence of multiple identical jobs. The key ingredients of the proposed approach are (1) an efficient processingtime-based dispatching rule, (2) simulation of a job shop, and (3) a mechanism to “fake” (or modify) job processing times based on the information of job slack obtained from simulation. The paper presents an overall approach to fake processing times, and also identifies alternative strategies for algorithm design. Experimental results of the proposed approach yield a dispatching priority with more than 10% better due date performance than the priority generated by a good processing-time-based dispatching rule in roughly 20 simulation runs.

This paper presents a simulation-optimization approach to find an appropriate dispatching priority. The study is based on a detailed simulator for a module-type commercial FMS. Specifically, after presenting the basic configuration and fundamental control logic of the system together with its main characteristics as a special type of a job shop, an algorithm is presented which combines simulated annealing and simulation to explore a dispatching priority of operations that minimizes the total tardiness. Computational performance of the algorithm is presented which shows that good solutions can be obtained mostly after 300 iterations or so. The paper also compares the performance of the optimal" or near optimal dispatching priority generated by the proposed algorithm with those generated by standard dispatching rules. The results show that standard dispatching rules such as EDD and SLACK which take due dates into considerations perform moderately, but not extremely well. The results also show that some of the workload-based dispatching rules such as SPT work consistently well.

Described in this paper is an application of a discrete-event simulation model for the Mazatrol FMS system manufactured by Yamazaki Mazak, one of the leading machine tool companies in the world, to analyze various causes of machine idle times. The Mazatrol FMS is a module-type FMS which consists of the maximum of 8 horizontal machining centers, 1 to 4 load/unload stations, a stacker crane, pallet stockers among others. Presentation of a conceptual framework for the machine idle times and their causes is followed by detailed simulation results. Simulation indicates that the utilization of machining centers during the normal operating period is at least 92.7% and is reasonably high, under the conditions of enough work load for each machine and no equipment failure. It is also shown that the main causes of the machine idle times differ depending on the periods in which they occur during the entire makespan. The increase of routing flexibility, which is known to be an important factor for the reduction of the makespan, is found to give little effect on the machine utilization. On the other hand, the results show that the number of pallets is an important factor for high machine utilization. The simulation results are expected to provide useful information for efficient operation of FMSs in general, and of the Mazatrol FMS in particular. Suggestions are given on how simulation results could be used to improve the system utilization on the medium-range as well as the short-term planning of FMSs.

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.

An apparently difficult, yet small, integer program has been tested on what we believe to be is a most efficient computer system containing a group theoretic algorithm. Although a good solution was produced, the code did not converge in at most thirty seconds of UNIVAC 1108 time, and thus the integer program can serve as a principal test problem. The model represents a real world chemical blending situation and was received from E. I. DuPont DeNemours & Co., Inc.

Two or more radio signals, transmitted from a small platform (e.g., a ship, satellite, or airplane, etc.), tend to produce an intermodulation product which could distort a receive signal. The intensity of intermodulation interference due to a given intermodulation frequency is known to be closely related to the lowest order, or simply the order, of the intermodulation product which can be found by solving a single constraint integer program with variables unrestricted in sign, where coefficients of the constraint equation correspond to frequencies. Two variations of backtrack, or search enumeration, algorithms, called the primal and dual backtrack algorithms, are developed to find the order of intermodulation. Extensive computational experience with these algorithms, reflecting data from naval fleet communication scenarios and potential ramifications, are given together with another application of the dual algorithm.

This paper describes how a dentist can use a new management tool, a computerized dental practice management game, to plan his or her own practice. After reviewing factors to be considered in planning a dental practice, we briefly describe the game with special emphasis on what it can and cannot do. After identifying the information required to make such an exercise useful in planning a specific practice, the paper gives an example that shows how the game can be so used.

This paper shows that the Blankinship algorithm, originally proposed to find the greatest common divisor of several integers and a solution of the associated linear diophantine equation, can be used to find the general solution of the equation. This yields a more efficient method to find the general solution than the one proposed by Bond. The modification of Blankinship's algorithm to avoid generating vectors with huge component values is also proposed.

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.

A common problem frequently faced by business firms and individual investors is to select a few investment opportunities from many available possibilities. This problem, in its simplest form, can be modeled as a 0–1 knapsack problem. In a more general investment scenario, however, we obtain a model which is a general knapsack problem with a multiple-choice constraint. To solve this problem, an efficient enumerative algorithm is developed. The algorithm includes an efficient procedure to solve the LP-relaxed problem, a reduction algorithm which may allow the initial fixing of some of the variables, and various other implicit enumeration criteria derived from the group problem. Extensive computational experience illustrates the efficiency of the algorithm and related results.

This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.

Product transportation and storage in steel works are modeled in order to evaluate both facility specification and transportation rules. Discrete-event simulation together with mathematical optimization technique are carried out based on probability distribution which is determined by analysis of actual operating data. The model utilizes a combined network and discrete-event approach written under the SLAM II simulation language. Simulation results show that the proper configuration of facilities and suitabIe transportation rules contribute to the carriage efficiency and lead to the great reduction of transportation cost in steel works .

This paper describes the structure of a dental practice management game. The game covers a wide spectrum of management decisions in setting up and in running a dental practice. The decisions considered include practice location, the form of practice, staffing mix, salaries, and the purchasing or leasing of equipment. The game also covers major daily, monthly, and yearly decisions including forecasting patient load, economic analysis, and scheduling of patients, workers, and operatories. The paper also discusses the cost and time required to run the game. Many sample printouts are included.

A disaggregation of the production planning in an injection molding industry is considered. The production is completely determined by orders, rather than sales forecast, and an enormous number of different products are involved. A disaggregation problem is identified with emphasis on levels II and III decisions. A simulation approach is considered for level II planning, which plays a major role in disaggregation. We show that disaggregation is the result of various logistical, technological, and computational considerations. The concept of search enumeration in integer programming is applied for level III scheduling. All work discussed here relates to part of an actual case study for a medium size Ohio corporation and resulted in the development of a computer system for order processing, production planning and scheduling, and inventory control.

A group theoretic algorithm for the integer program has been computer programmed and tested. It basically consists of a linear programming algorithm, a routine which converts the (relaxed) integer program to a group minimization problem (over the fractional column group or the isomorphic factor group attained via Smith's Normal Form), solving the group problem by dynamic programming or by a shortest path algorithm, and when necessary, uses a branch and bound procedure. Details and computational results are given. Future work regarding other computational strategies available to group theoretic algorithms is also included.