Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

A genetic algorithm for service level based vehicle scheduling

In many practical applications, vehicle scheduling problems involve more complex evaluation criteria than simple distance or travel time minimization. Scheduling to minimize delays between the accumulation and delivery of correspondence represents a class of vehicle scheduling problems, where: the evaluation of candidate solutions is costly, there are no efficient schemes for evaluation of partial solutions or perturbations to existing solutions, and dimensionality is limiting even for problems with relatively few locations. Several features of genetic algorithms (GA's) suggest that they may have advantages relative to alternative heuristic solution algorithms for such problems. These include ease of implementation through efficient coding of solution alternatives, simultaneous emphasis on global as well as local search, and the use of randomization in the search process. In addition, a GA may realize advantages usually associated with interactive methods by replicating the positive attributes of existing solutions in the search process, without explicitly defining or measuring these attributes. This study investigates these potential advantages through application of a GA to a service level based vehicle scheduling problem. The procedure is demonstrated for a vehicle scheduling problem with 15 locations where the objective is to minimize the time between the accumulation of correspondence at each location and delivery to destination locations. The results suggest that genetic algorithms can be effective for finding good quality scheduling solutions with only limited search of the solution space.     

A time–space network based exact optimization model for multi-depot bus scheduling

The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and waiting time. This paper discusses the multi-depot, multi-vehicle-type bus scheduling problem (MDVSP), involving multiple depots for vehicles and different vehicle types for timetabled trips. We use time–space-based instead of connection-based networks for MDVSP modeling. This leads to a crucial size reduction of the corresponding mathematical models compared to well-known connection-based network flow or set partitioning models. The proposed modeling approach enables us to solve real-world problem instances with thousands of scheduled trips by direct application of standard optimization software. To our knowledge, the largest problems that we solved to optimality could not be solved by any existing exact approach. The presented research results have been developed in co-operation with the provider of transportation planning software PTV AG. A software component to support planners in public transport was designed and implemented in context of this co-operation as well.     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.     

TRACS II: a hybrid IP/heuristic driver scheduling system for public transport

We discuss the driver scheduling problem in public transport and describe a combined integer linear programming/heuristic approach to its solution. The approach has been applied successfully in many operational and planning scenarios. Recent developments in the algorithms used allow the solution of very large bus and rail problems.     

Genetic Algorithm for the Jump Number Scheduling Problem

This paper introduces genetic algorithms for the jump number scheduling problem. Given a set of tasks subject to precedence constraints, the problem is to construct a schedule to minimize the number of jumps. We show that genetic algorithms outperform the previously known Knuth and Szwarcfiter's exhaustive search algorithm when applied to some classes of orders in which no polynomial time algorithms exist in solving the jump number problem. Values for various parameters of genetic jump number algorithms are tested and results are discussed.     

Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed

This paper considers two single-machine scheduling problems with outsourcing allowed where each job can be either processed on an in-house single-machine or outsourced. They include the problem of minimizing maximum lateness and outsourcing costs, and that of minimizing total tardiness and outsourcing costs. Outsourcing is commonly required as a way to improve productivity in various companies including electronics industries and motor industries. The objective is to minimize the weighted sum of the outsourcing cost and the scheduling measure represented by either one of maximum lateness and total tardiness, subject to outsourcing budget. It is proved that the problem is NP-hard. Some solution properties are characterized to derive heuristic algorithms, and also a branch-and-bound algorithm. Numerical experiments are conducted to evaluate performance of the derived algorithms.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.     

A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

Fast local search and guided local search and their application to British Telecom's workforce scheduling problem

This paper reports a fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search (GLS) algorithm which was developed to help local search to escape local optima and distribute search effort. To illustrate how these algorithms work, this paper describes their application to British Telecom's workforce scheduling problem, which is a hard real life problem. The effectiveness of FLS and GLS are demonstrated by the fact that they both outperform all the methods applied to this problem so far, which include simulated annealing, genetic algorithms and constraint logic programming.     

Linear Time Algorithms for Parallel Machine Scheduling

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.     

The Container Transshipment Problem: Searching Representation Landscapes with Metaheuristic Algorithms

The container transshipment problem involves scheduling a fleet of lorries to collect and deliver containers of various sizes while minimizing the total distance travelled. The problem originates in the need for logistics companies to solve the problem on a regular basis as part of their daily operations. In this paper, we compare two genetic algorithms tailored to solve this problem based on permutation and bin-packing inspired encodings. Results are presented and analysed in order to evaluate the validity and robustness of the two approaches. As part of the analysis, bounds were calculated to determine how well both GAs perform in absolute terms as well as relative to each other. Of the two GA there is one clear winner, although it is not the one that would have been indicated by previous research. Whilst the winning GA is able to generate significant savings in practice, compared to the optimum there remains room for further improvement.     

Metaheuristics approach for solving personalized crew rostering problem in public bus transit

The crew rostering problem in public bus transit aims at constructing personalized monthly schedules for all drivers. This problem is often formulated as a multi-objective optimization problem, since it considers the interests of both the management of bus companies and the drivers. Therefore, this paper attempts to solve the multi-objective crew rostering problem with the weighted sum of all objectives using ant colony optimization, simulated annealing, and tabu search methods. To the best of our knowledge, this is the first paper that attempts to solve the personalized crew rostering problem in public transit using different metaheuristics, especially the ant colony optimization. The developed algorithms are tested on numerical real-world instances, and the results are compared with ones solved by commercial solvers.     

基于启发式Q学习的汽车涂装车间作业排序优化

针对汽车涂装车间中的作业优化排序问题,提出一种基于启发式Q学习的优化算法。首先,建立包括满足总装车间生产顺序和最小化喷枪颜色切换次数的多目标整数规划模型。将涂装作业优化排序问题抽象为马尔可夫过程,建立基于启发式Q算法的求解方法。通过具体案例,对比分析了启发式Q学习、Q学习、遗传算法三种方案的优劣。结果表明：在大规模问题域中,启发式Q学习算法具有寻优效率更高、效果更好的优势。本研究为机器学习算法在汽车涂装作业优化排序问题的应用提出了新思路。     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

Heuristics Ancient and Modern: Transport Scheduling Through the Ages

Heuristics which have been developed for transport scheduling over a lengthy period starting in 1960 are presented. They are generated in response to requirements to solve practical problems, and most are now in regular use by bus and train companies. Mathematical programming models have been formulated for some of the problems, but have been inappropriate on their own; in some cases, heuristics have led to a reduced problem which has then been solved by integer linear programming. The paper is designed to illustrate the development of heuristics for a range of related problem areas over nearly forty years. It explores the relationships between heuristics and other approaches and emphasises the need to convince users of the suitability of the overall system. Where appropriate, indications are given of difficulties in achieving practical implementation.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.