招待講演
Tuesday, July 18, 13:30-14:30
Gate Scheduling at Airports
Erwin Pesch
Institute of Information Systems, University of Siegen, Germany
Abstract: Flight-gate scheduling is concerned with finding an assignment of flights to terminal or ramp positions, called gates, and an assignment of the start and completion times of the processing of a flight at its position.
A good assignment may reduce the number of aircraft tows required and may lead to reduced setup times for several ground service activities on the ramp as well as in the terminal.
The key idea behind the model presented here is to look at the problem as a modified multi-mode resource-constrained project scheduling problem with a multi-criteria objective function. The most important goals are the maximization of a total flight-gate preference value and the minimization of the number of tows. The basic optimization algorithm is a truncated branch-and-bound procedure that branches over gate assignments and the disjunctive constraints used to model the capacity restrictions of the disjunctive resources (gates). The algorithm uses constraint propagation techniques to reduce the search space. To cope with large practical problems within the order of magnitude of thousand flights per day, the problem is decomposed into loosely coupled subproblems using a new generic problem partitioning technique. The subproblems are used within a layered branch-and-bound approach: The search tree is conceptually split into layers that correspond to the subproblems. In each layer, only decision variables of the current subproblem are selected for branching; limited backtracking is performed within the current layer before proceeding to the next layer. Initial solutions obtained in this way are iteratively improved using a Large Neighbourhood Search technique that relaxes some of the decisions and uses the branch-and-bound algorithm to reform the relaxed part of the solution at a lower cost. The model and algorithm have been evaluated using small manually designed test cases as well as two weeks of a real-life flight schedule from a large international airport. A comparison of the computational results with a rule based approach, as often used in commercial systems, shows that the algorithm greatly improves the solution quality.
Wednesday, July 19, 11:40-12:40
Production Scheduling to Decrease Transportation Costs
Kathryn E. Stecke
School of Management, University of Texas at Dallas, USA.
Abstract: When make-to-order manufacturing company adopts a commit-to-delivery business mode, it commits a delivery due date for an order and is responsible for the shipping cost. Without loss of generality, we consider that transportation is done by a third party logistics company such as FedEx or UPS, which provides multiple shipping modes such as overnight, one-day, two-day delivery, and more. When the transportation time has to be short, clearly shipping cost is more expensive than it could have been. How should a company schedule production for all accepted orders so that the company can leave enough transportation time for orders to take slow shipping modes to reduce the shipping cost? We study this problem of integrating the production and transportation functions for a manufacuturing company producing a variety of customized products in a make-to-order environment with a commit-to-delivery mode of business.
Various realistic scenarios are investigated, in increasing order of complexity. When partial delivery is allowed by customers, we provide both an MIP model and a minimum cost flow model. We show that nonpreemptive EDD production schedules are optimal when partial delivery is allowed and shipping cost is a decreasing convex function with transportation time. When partial delivery is not allowed, we develop an MIP model and prove that the problem is NP-hard. An efficient heuristic algorithm with polynomial computation time is provided for the NP-hard problem. It gives near-optimal production schedules, as shown via many numerical experiments. We also provide models and analysis for order scenarios where shipping cost accounts for cunstomer locations and quantity discounts.
Thursday, July 20, 11:20-12:20
Cyclic Machine Scheduling: A General Framework
Peter Brucker and Thomas Kampmeyer
University of Osnabrueck, Germany
Abstract: Cyclic versions of job-shop (or flow-shop) scheduling problems with special features like positive and negative time-lags or blocking and non-blocking situations are considered. Furthermore, transportation may be taken into account. The objective is to minimize the cycle time. The model covers different cyclic versions of the job-shop problem found in the literature, robotic cell problems, and the single hoist scheduling problem.
It is shown that all these problems can be formulated as mixed integer linear programs which have a common structure. Small instances are solved with CPLEX. For larger instances tabu search procedures have been developed.
The same concepts can be used to solve cyclic scheduling problems with identical parallel machines and tool transportation between the machines, and computer pipelining problems.
|