An Algorithm for Bus Scheduling Problems

The problem arose in the context of devising a schedule for buses to be operated by a State Transport Corporation. An algorithm for obtaining a schedule to minimize the number of buses required is described, in which computational advantage is taken of the special structure of the problem. A computer program has been written and some results of its use are described.     

Combining Constraint Programming and Linear Programming on an Example of Bus Driver Scheduling

This paper provides details of a successful application where the Column Generation algorithm was used to combine Constraint Programming and Linear Programming. In the past, constraint programming and linear programming were considered to be two competing technologies that solved similar types of problems. Both these technologies had their strengths and weaknesses. This paper shows that the two technologies can be combined together to extract the strengths of both these technologies. Details of a real-world application to optimize bus driver duties is given here. This system was developed by ILOG for a major software house in Japan using ILOG-Solver and ILOG-CPLEX, constraint programming and linear programming C/C++ libraries.     

排序、经典排序和新型排序

本文简略地介绍排序,经典排序和新型排序．     

Overtime Scheduling: An Application in Finite-capacity Real-time Scheduling

Negotiating and meeting due-times for work-orders is often the most important concern of managers of manufacturing systems. We propose a new approach called overtime scheduling that determines on which work-centres, when and how much overtime is required to meet a requested due-time with minimum overtime cost. This method would be used as a part of a finite-capacity real-time scheduling and planning system. We propose a work-order insertion based approach, where a new work-order is scheduled without substantially changing the schedule of previously scheduled work-orders. Based on this approach, we characterise the solution space and present experimental results on the performances of several heuristics.     

单机供应链排序及流水作业的反问题模型

最优化问题是在给定参数情况下,对某个目标函数,如费用、容量等,寻找问题的最优解.然而在许多现实生活中,有时只能知道问题的参数近似值和一个可行解,需要最小程度地调整参数,使得给定的可行解成为最优,这就是最优化问题的反问题.本文研究单台机器供应链排序和流水作业排序的反问题.根据调整参数的不同,本文利用排序理论把这些反问题表示为相应的数学规划形式.     

Bus Fares Pricing

Transport pricing at the level of the firm is addressed. The numbers of full fare passengers travelling on three routes of two competing bus companies are analysed using a multiplicative discontinuous price model. Results show that generally only the operator increasing the price suffers a loss of passengers and the price elasticity is a non-linear function of the resulting price difference. The method of analysis and the results have implications for the market modelling of fast moving consumer goods. It is noted that almost no studies of transport pricing at the level of the firm have been carried out previously because of lack of data.     

Fairness in Scheduling

On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long-lived processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion ofdesiredload of a process, which is a function of the tasks it participates in. Theunfairnessof a system is the maximum, taken over all processes, of the difference between the desired load and the actual load.An example of such a setting is thecarpool problemsuggested by Fagin and Williams [IBM Journal of Research and Development27(2) (1983), 133–139]. In this problem, a set ofnpeople form a carpool. On each day a subset of the people arrive and one of them is designated as the driver. A scheduling rule is required so that the driver will be determined in a “fair” way.We investigate this problem under various assumptions on the input distribution. We also show that the carpool problems can capture several other problems of fairness in scheduling.     

Scheduling surgical procedures

The scheduling of surgical procedures in hospitals is examined in the context of an optimisation problem. The solution procedure proposed uses simulated annealing to find improved solutions. An assessment of current practice reveals that customising of any automated procedure will be necessary as the constraints used to describe the problem are often hospital specific.     

Scheduling charter aircraft

We present a system that is used for scheduling charter aircraft. At the core of the system is an elastic set partitioning model that is embedded in a decision support system. The model assigns a set of flights that have to be performed to the available fleets of aircraft at minimal cost while satisfying all operational requirements. Flights that cannot be accommodated by the available fleets are sold off to other operators. The minimised costs include the cost of flying the aircraft, the cost of selling off flights, and penalties on violations of soft constraints. The system has been in daily operation for almost a year, and it provides high quality schedules and saves numerous hours to the schedulers.     

Scheduling farm operations

Scheduling operations on a farm is considered depending on the available men and machinery and on the influence of the weather on materials (moisture content). A simulation model with a heuristic strategy for selecting operations at each moment of decision based on the state of the system and a linear programming model are used in the grain harvest to demonstrate the influence of the models on the resulting variable costs (overtime, drying of wet grain and timeliness losses of wheat and straw) and the influence of input data (weather, attributes of material and number of workable hours) on those costs. The lower costs found with simplified input (hourly, daily, weekly data) in simulation is continued with the linear programming model due to its deviation from the real workable time constraints and decision variables. Such a tendency suggests that LP-models usual in agricultural planning are too simple.     

Vehicle Scheduling Revisited

Several published results for vehicle scheduling algorithms are based on rounded inter-customer distances. This gives overall distances which vary somewhat from actual distances (presented here), and there appears to be a downward bias. Care should be taken in comparing results based on rounded inter-customer distances with those based on real distances.     

活动执行时间可提前的多模式反应性项目调度优化

研究不确定活动工期下活动执行时间可提前的多模式反应性项目调度问题。首先对反应性研究现状进行综述;其次建立以最小化反应性总成本为目标的优化模型;随后基于问题特点设计禁忌搜索算法;最后通过具体案例分析关键参数对反应性成本的影响,并得出结论:执行时间提前得到的反应性成本及完工时间明显低于执行时间不可提前的结果;随着项目推进,总成本及影响的活动数量总体上呈减小趋势,但项目完工时间在某些时刻维持不变;对于工期增加较大的活动,将其本身或紧前活动提前启动,或将其转换至活动工期较短的模式可降低反应性成本。研究可为不确定环境下反应性计划制定提供决策支持。