Dissertations / Theses on the topic 'Train Scheduling and Rescheduling'

Train dispatchers faces lots of challenges due to conflicts which causes delays of trains as a result of solving possible dispatching problems the network faces. The major challenge is for the train dispatchers to make the right decision and have reliable, cost effective and much more faster approaches needed to solve dispatching problems. This thesis work provides detail information on the implementation of different heuristic algorithms for train dispatchers in solving train dispatching problems. The library data files used are in xml file format and deals with both single and double tracks between main stations. The main objective of this work is to build different heuristic algorithms to solve unexpected delays faced by train dispatchers and to help in making right decisions on steps to take to have reliable and cost effective solution to the problems. These heuristics algorithms proposed were able to help dispatchers in making right decisions when solving train dispatching problems.

La Flatland challenge è una competizione che ha come obiettivo incentivare la ricerca nell'ambito del reinforcement learning multi agente (MARL) applicato ai problemi di re-scheduling (RSP). Lo scopo della sfida è sviluppare soluzioni per la gestione di una flotta di treni su una vasta rete ferroviaria, in modo che gli agenti si coordinino e collaborino per raggiungere ciascuno la propria destinazione nel minor tempo possibile, anche in caso si verifichino guasti temporanei. Il rescheduling è un problema complesso già affrontato in varie forme e con vari approcci, la Flatland challenge lo ripropone fornendo un ambiente per effettuare simulazioni del traffico ferroviario, con lo scopo di incentivare lo sviluppo di nuove soluzioni basate su reinforcement learning. In questo elaborato si affrontano i problemi di navigazione e rescheduling di treni posti dalla sfida, utilizzando un approccio basato sul reinforcement learning multi-agente (MARL). Viene descritto come, attraverso l'uso di tecniche di Deep Q-learning e una rappresentazione dello stato dell'ambiente sotto forma di bitmap, siano stati ottenuti risultati promettenti.

The issue of managing a large and complex railway system with continuous traffic flows and mixed train services in a safe and punctual manner is very important, especially after disruptive events. In the first part of this thesis an analysis method is introduced which allows the visualisation and measurement of the propagation of delays in the railway network. The BRaVE simulator and the University of Birmingham Single Train Simulator (STS) are also introduced and a train running estimation using STS is described. A practical single junction rescheduling problem is then defined and it investigates how different levels of delays and numbers of constraints may affect the performance of algorithms for network-wide rescheduling in terms of quality of solution and computation time. In order to deal with operational dynamics, a methodology using performance-based supervisory control is proposed to provide rescheduling decisions over a wider area through the application of different rescheduling strategies in appropriate sequences. Finally, an architecture for a real-time train rescheduling framework, based on the distributed artificial intelligence system, is designed in order to handle railway traffic in a large-scale network intelligently. A case study based on part of the East Coast Main Line is followed up to demonstrate the effectiveness of adopting supervisory control to provide the rescheduling options in the dynamic situation.

The awareness for the schedule modification under process disturbances so-called rescheduling, has been growing in the area of chemical batch plants. For the last three decades, planning and scheduling have played a practical and crucial role in not only reducing the inefficiency of batch operations, but also increasing the productivity of batch plants. However, the off-line planning/scheduling can be very inefficient, or even infeasible to be performed when particularly certain undesirable disturbances occur during the operation period. In these cases, therefore, the schedule modification will be inevitably required to reduce or minimise the effects of the disturbances arisen. In this sense, a systematic methodology for the schedule modification is needed to support and guide decision-makers and operators. The development of the methodology is the main objective of this thesis, and the focus mainly lies on the integration between scheduling and rescheduling for chemical batch plants. Two different scheduling algorithms have been proposed in this thesis. The formulation (Model I) based on the concept of State-Task Network (STN) is proposed for the scheduling of multipurpose batch processes, while Model II facilitates the scheduling of multiple product batch plants. Both algorithms are based on the deterministic methods, and the global optimality can be guaranteed. Although Model I is formulated as a Mixed Integer Non-Linear Programming (MINLP) problem, the global optimality of Model I is guaranteed due to the convexity proved. On the other hand, Model II results in a Mixed Integer Linear Programming (MILP), hence the global optimality guaranteed. The performances of the scheduling algorithms are far better than other precedent algorithms, and the details of the computational results are shown in the corresponding sections. In particular, these two scheduling algorithms are reutilised as a deterministic-based rescheduling algorithms after certain modification such as fixing variables, adding or removing constraints, change of an objective function, etc. These modifications are highly dependent upon the given conditions, namely, case-by-case basis. Nevertheless, it provides us the good concept in the sense that the global optimality for the rescheduling can be guaranteed if non-convexity does not take place in the models by the modifications. As far as the global optimality for scheduling and rescheduling is guaranteed, the difference between scheduling and rescheduling will be the minimum (or maximum) effect caused by the disturbance occurred. On the other hand, heuristic or rule-based methods have advantages for the simplicity of the adaptation and/or the similarity with the original schedule, even though their optimality is not guaranteed. In multiple product batch plants, a rule-based method by using completion time algorithm is proposed for the processing time delays and unit failures. In contrast, a rule-based method for multipurpose batch processes is based on the recalculation of material balances that will be required for accommodating the losses of intermediates. For the selection of a rescheduling option against the disturbances arisen, the variability test has been performed in order to identify the most sensitive process variability, so called key variability. To identify the key variability, the accumulated loss of profit function has been introduced as a performance index. Then, the key variability against a process variation occurred has been determined by a variation with maximum index. Based on the key variability identified, the determination of a rescheduling option is made by the rescheduling methodology proposed. From the various examples tested, it is shown the that the approach proposed enables to guide for the selection of rescheduling options available by using the concept of key variability, and the identification of key variability provides good guidelines for decision-making of reactive schedule modification.

Durante il quotidiano svolgersi del servizio ferroviario, possono verificarsi eventi imprevisti, come un guasto o un ritardo, che rischiano di pregiudicare la validità dell'orario ferroviario stabilito. Quando ciò avviene, è necessario individuare delle azioni correttive da compiere per riportare la rete ferroviaria in uno stato compatibile con i requisiti di sicurezza, che si discosti il meno possibile dall'orario originale. In questo elaborato, dopo aver formalizzato il real-time Train Rescheduling Problem (rtTRP), proponiamo la formulazione di un modello di programmazione lineare mista-intera per individuare la soluzione ottima del problema e presentiamo i risultati di una serie di test computazionali effettuati su istanze reali, utilizzando le soluzioni trovate per valutare le performance di un algoritmo attualmente in uso nel mondo industriale.

This thesis deals with optimisation approaches for the train unit scheduling problem (TUSP). Given a train operator’s fixed timetables and a fleet of train units of different types, the TUSP aims at determining an assignment plan such that each train trip in the timetable is appropriately covered by a single or coupled units, with certain objectives achieved and certain constraints respected. From the perspective of a train unit, scheduling assigns a sequence of trains to it as its daily workload. The TUSP also includes some auxiliary activities such as empty-running generation, coupling/decoupling control, platform assignment, platform/siding/depot capacity control, re-platforming, reverse, shunting movements from/to sidings or depots and unit blockage resolution. It is also relevant with activities like unit overnight balance, maintenance provision and unit rostering. In general, it is a very complex planning process involving various aspects. Current literature on optimisation methods for the TUSP is very scarce, and for those existing ones they are generally unsuitable for the UK railway industry, either due to different problem settings and operational regulations or simplifications on some critical factors in practice. Moreover, there is no known successful commercial software for automatically optimising train unit scheduling in the world as far as the author is aware, in contrast with bus vehicle scheduling, crew scheduling and flight scheduling. This research aims at taking an initial step for filling the above gaps. A two-level framework for solving the TUSP has been proposed based on the connection-arc graph representation. The network-level as an integer multicommodity flow model captures the essence of the rail network and allocates the optimum amount of train unit resources to each train globally to ensure the overall optimality, and the station-level process (post-processing) resolves the remaining local issues like unit blockage. Several ILP formulations are presented to solve the network-level model. A local convex hull method is particularly used to realise difficult requirements and tighten LP relaxation and some further discussions over this method is also given. Dantzig-Wolfe decomposition is used to convert an arc formulation to a path formulation. A customised branch-and-price solver is designed to solve the path formulation. Extensive computational experiments have been conducted based on real-world problem instances from ScotRail. The results are satisfied by rail practitioners from ScotRail and are generally competitive or better than the manual ones. Experiments for fine-tuning the branch-and-price solver, solution quality analysis, demand estimation and post-processing have also been carried out and the results are reported. This research has laid a promising foundation leading to a continuation EPSRC funded project (EP/M007243/1) in collaboration with FirstGroup and Tracsis plc.

Scheduling of Train Unit Cleaning is one of the planning processes required at DSB, The Danish Railway Company. In order to ensure an adequate service level to its customers, train cleaning must be planned as efficiently as possible. The presence of several decision variables and even more constraints requires the utilization of a tool to ensure the respect of all the requests while cost of operations is minimized. This thesis project proposes an optimisation model to solve the train cleaning scheduling problem. A mathematical formulation based on a space-time network describing the movement of the rolling stock is presented. A Label Setting Algorithm based on this network can solve to optimality the reduced scheduling problem associated with each train unit. In order to obtain a cleaning operation plan for all the train set, the Label Setting Algorithm generates it in a recursive way and a heuristic approach verifies the respect of further restrictions. The algorithm was tested on real instances from DSB. The main parameters of evaluation were the total time of execution of the cleaning operations and the service level provided. The Label Setting Algorithm with its flexibility has permitted us to implement different assumptions on parameters. In each of these situation the proposed model has generated good results in terms of cost minimization. The use of a greedy heuristic approach in a second stage has demonstrated to be the weakest part of the approach, on which future improvement can be considered.

Train driver scheduling is the problem of finding an assignment of drivers to cover all train vehicle work, such that cost is minimized while all constraints are satis¯ed. Relieving of drivers happens mostly at train stops; in many cases the train will stop for several minutes, giving rise to a window of relief opportunities (WRO), but current industry practice is to consider relieving only at the time the train arrives at the station. This thesis studies an extension of the train driver scheduling problem to exploit relieving drivers within WROs at times other than the arrival. While extending the problem in this way may lead to a more expressive model, and better solutions, it also gives rise to problem sizes too large for existing scheduling methods. Two different approaches to solve the problem of driver scheduling with WROs are presented. In the first, relief opportunities inside WROs are evaluated in terms of their role in generating solutions unavailable to the relief-on-arrival formulation. Heuristics based on this evaluation result in instance sizes that are manageable with current generate-and-select (GaS) methods. Experiments produce new best-known solutions for some real-life instances of the problem. The second approach is a hybridized system that generates an initial solution using GaS on a relief-on-arrival formulation, which is fed into a local search method running on a full WRO model. This method is then extended by allowing infeasible solutions to be considered during the search. A novel way of costing infeasible solutions is introduced, where the cost of an infeasible solution is derived from a repaired, feasible version of that solution. This strategy is embedded in a local search framework that alternates between exploration of feasible and infeasible regions, where infeasibility arises from complex moves that remove undesirable structural features in the current feasible solution.

This Thesis aims to provide a literature review on Energy-Efficient Train Control (EETC) and Energy-Efficient Timetabling (EETT). Solving EETC and EETT problems, although highly complex, is crucial in order to implement decision support systems for reducing energy consumption and environmental impact in railway networks. Relevant mathematical models and algorithms applicable for the problems at study are presented along with their pros and cons. Moreover, the Pontryagin's Maximum Principle, on which many models and solution approaches are based upon, is briefly introduced. The first chapter offers an overview of both EETC and EETT, the second focuses on single-train Energy Efficient Train Control, the third provides our conclusions. The recent survey by Scheepmaker et al. (2017) inspired our presentation of topics.

Nowadays, transforming the railway industry for better performance and making the best usage of the current capacity are the key issues in many countries. Operational research methods and in particular scheduling techniques have a substantial potential to offer algorithmic solutions to improve railway operation and control. This thesis looks at train scheduling and rescheduling problems in a microscopic level with regard to the track topology. All of the timetable components are fixed and we aim to minimize delay by considering a tardiness objective function and only allowing changes to the order and to the starting times of trains on blocks. Various operational and safety constraints should be considered. We have achieved further developments in the �eld including generalizations to the existing models in order to obtain a generic model that includes important additional constraints. We make use of the analogy between the train scheduling problem and job shop scheduling problem. The model is customized to the UK railway network and signaling system. Introduced solution methods are inspired by the successful results of the shifting bottleneck to solve the job shop scheduling problems. Several solution methods such as mathematical programming and different variants of the shifting bottleneck are investigated. The proposed methods are implemented on a real-world case study based on London Bridge area in the South East of the UK. It is a dense network of interconnected lines and complicated with regard to stations and junctions structure. Computational experiments show the effciency and limitations of the mathematical programming model and one variant of the proposed shifting bottleneck algorithms. This study also addresses train routing and rerouting problems in a mesoscopic level regarding relaxing some of the detailed constraints. The aim is to make the best usage of routing options in the network to minimize delay propagation. In addition to train routes, train entry times and orders on track segment are defined. Hence, the routing and scheduling decisions are combined in the solutions arising from this problem. Train routing and rerouting problems areformulated as modified job shop problems to include the main safety and operational constraints. Novel shifting bottleneck algorithms are provided to solve the problem. Computational results are reported on the same case study based on London Bridge area and the results show the efficiency of one variant of the developed shifting bottleneck algorithms in terms of solution quality and runtime.

In this doctoral thesis, four questions related to computational geometry are considered. The first is an extremal combinatorics question regarding triangles with vertices taken from a set of n points in convex position. More precisely, two such triangles can exhibit eight distinct configurations and, for each subset of these configurations, we are interested in the asymptotics of how many triangles one can have while avoiding configurations in the subset (as a function of n). For most of these subsets, we answer this question optimally up to a logarithmic factor in the form of several Turán-type theorems. The answers for the remaining few were in turn tied to that of a long-standing open problem which appeared in the literature in the contexts of monotone matrices, tripod packing and 2-comparable sets. The second problem, called Line Segment Covering (LSC), is about covering the cells of an arrangement of line segments with these line segments, where a segment covers the cells it is incident to. Recently, a PTAS, an APX -hardness proof and a FPT algorithm for variants of this problem have been shown. This paper and a new slight generalization of one of its results is included as a chapter. The third problem has been posed in the Sixth Annual Workshop on Geometry and Graphs and concerns the design of road networks to minimize the maximum travel time between two point sets in the plane. Traveling outside the roads costs more time per unit of distance than traveling on the roads and the total length of the roads can not exceed a budget. When the point sets are the opposing sides of a unit square and the budget is at most √2, we were able to come up with a few network designs that cover all possible cases and are provably optimal. Furthermore, when both point sets are the boundary of a unit circle, we managed to disprove the natural conjecture that a concentric circle is an optimal design. Finally, we consider collision-avoiding schedules of unit-velocity axis-aligned trains departing and arriving from points in the integer lattice. We prove a few surprising results on the existence of constant upper bounds on the maximum delay that are independent of the train network. In particular, these upper bounds are shown to always exist in two dimensions and to exist in three dimensions for unit-length trains. We also showed computationally that, for several scenarios, these upper bounds are tight.

Context. Train re-scheduling during disturbances is a time-consuming task. Modified schedules need to be found, so that trains can meet in suitable locations and delays minimized. Domino effects are difficult to manage. Commercial optimization software has been shown to find optimal solutions, but modied schedules need to be found quickly. Therefore, greedy depth-first algorithms have been designed to find solutions within a limited time-frame. Modern GPUs have a high computational capacity, and have become easier to use for computations unrelated to computer graphics with the development of technologies such as CUDA and OpenCL. Objectives. We explore the feasibility of running a re-scheduling algorithm developed specifically for this problem on a GPU using the CUDA toolkit. The main objective is to find a way of exploiting the computational capacity of modern GPUs to find better re-scheduling solutions within a limited time-frame. Methods. We develop and adapt a sequential algorithm for use on a GPU and run multiple experiments using 16 disturbance scenarios on the single-tracked iron ore line in northern Sweden. Results. Our implementation succeeds in finding re-scheduling solutions without conflicts for all 16 scenarios. The algorithm visits on average 7 times more nodes per time unit than the sequential CPU algorithm when branching at depth 50, and 4 times more when branching at depth 200. Conclusions. The computational performance of our parallel algorithm is promising but the approach is not complete. Our experiments only show that multiple solution branches can be explored fast in parallel, but not how to construct a high level algorithm that systematically searches for better schedules within a certain time limit. Further research is needed for that. We also find that multiple threads explore redundant solutions in our approach.

Healthcare is a unique industry in terms of the associated requirements and services provided to patients. Currently, healthcare industry is facing challenges of reducing the cost and improving the quality and accessibility of service. Operating room is one of the biggest major cost and revenue centers in any healthcare facility. In this study, we develop optimization models and the corresponding solution strategies for addressing the problem of scheduling and rescheduling of the elective patients for surgical operations in the operating room. In the first stage, scheduling of the elective patients based on the availability of the resources is optimized. The resources considered in the study are the availability of the operating rooms, surgical teams, and the beds/equipment in the downstream post anesthesia care units (PACUs). Discrete distributions governing surgical durations for selected surgical specialties are developed for representing variability for duration of surgery. Based on the distributions, a stochastic mathematical programming model is developed. It is indicated that with the increase of problem sizes, the model may not be solved by using a leading commercial solver for optimization problems. As a result, a heuristic solution approach based on genetic algorithm is also developed. It is found out that the genetic algorithm provides close results as compared to the commercial solver in terms of solution quality. For large problem sizes, where the commercial solver is unable to solve the problem due to the memory restrictions, the genetic algorithm based approach is able to find a solution within a reasonable amount of computation time. In the second stage, the rescheduling of the elective patients due to the sudden arrival of the emergency patients is considered. A mathematical programming model for minimizing the costs related with expanding the current capacity and disruption caused by the inclusion of the emergency patient is developed. Also, two different solution approaches are brought forward, one with using the commercial solver, and the other based on genetic algorithm. Genetic algorithm based approach can always make efficient decision regarding whether to accept the emergency patients and how to minimize the reshuffling effort of the original elective surgery schedule.<br>Department of Veterans Affairs; National Science Foundation (Award # 1126570)

The bus and train driver scheduling problem involves assigning bus or train work to drivers in such a way that all the bus or train work is covered and the number of drivers and duty costs are minimised. This is complicated by the fact that there are many restrictions on the duty generation. The generate-and-select approach is at present the most successful for bus and train driver scheduling. It involves generating a set of legal potential driver duties from which a minimal and most efficient subset is selected. Filtering rules are often applied so that the set of potential duties generated would not be prohibitively large. Moreover, windows of relief opportunities (WROs), which provide ranges of opportunities for relieving drivers, are beyond the capability of being handled by the existing systems. The usual practice is to consider one, sometimes two, discrete times within each time window. Optimality of solution is therefore compromised. The research presented in this thesis focuses on solving the driver scheduling problem with WROs using a constructive approach, which builds and refines a single schedule iteratively. Filtering rules are unnecessary under the approach. The 2-opt heuristic approach is first investigated, during which the potential of constructive heuristics is explored. Based on the experience, the Tabu Search meta-heuristic approach is then investigated. Multi-neighbourhoods and an appropriate memory scheme, which are essential elements of Tabu Search are designed and tailored for the driver scheduling problem with WROs. Alternative designs have been tested and compared with best known solutions drawn from real-life data sets. The tabu search approach is very fast, can handle WROs, and has achieved results comparable to those based on mathematical programming approaches. Taking advantage of WROs, it can improve best known solutions obtained by the existing systems. Consequently, it could be incorporated into existing systems to improve the solution by taking advantage of WROs.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados.<br>This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

Disturbances in the railway network are frequent and to some extent, inevitable. When this happens, the traffic dispatchers need to re-schedule the train traffic and there is a need for decision support in this process. One purpose of such a decision support system would be to visualize the relevant, alternative re-scheduling solutions and benchmark them based on a set of relevant train traffic attributes which quantify the effects of each solution. Currently, there are two research projects financed by the Swedish Transport Administration (i.e. Trafikverket) which focus on developing decision support to assist the Swedish train traffic managers: The STEG project and the EOT project. Within the STEG project, researchers at Uppsala University in co-operation with Trafikverket are developing a graphical user interface (referred to as the STEG graph). Within the EOT project, researchers at Blekinge Institute of Technology (BTH) are developing fast re-scheduling algorithms to propose to the Swedish train traffic dispatchers a set of relevant re-scheduling alternatives when disturbances occur. However, neither the STEG graph nor the EOT algorithms are at this point designed to evaluate, benchmark and visualize the alternative re-scheduling solutions. The main objective of this work is therefore to identify and analyze different train traffic attributes and how to use the selected relevant ones for benchmarking re-scheduling solutions. This involves enhancing an existing visual tool (EOT GUI) and using this extended version (referred to as the EOT GUI+) to demonstrate and evaluate the benchmarking of different re-scheduling solutions based on the selected train traffic attributes. The train traffic attributes found in the literature (foremost research publications and documents by Trafikverket) were collected and analyzed. A subset of the most commonly used attributes found were then selected and their applicability in benchmarking re-scheduling solutions for the Swedish train traffic system was further analyzed. The formulas for calculating each of the attribute values were either found in the literature and possibly modified, or defined within this thesis project. In order to assess the use of the attributes for benchmark solutions, experiments were conducted using the enhanced visual tool EOT GUI+ and a set of sample solutions for three different disturbance scenarios provided by the EOT project. The tool only performs a benchmark of two solutions at a time (i.e. a pair wise benchmark) and computes the attribute values for the chosen attributes. The literature review and attribute analysis resulted in a first set of ten different attributes to use including e.g. total final delay (with a delay threshold value of 1 and 5 minutes respectively), maximum delay, total accumulated delay, total delay cost, number of delayed trains and robustness. The formulas to compute these attribute values were implemented and applied to the sample solutions in the experiments. The first phase of the experiments showed that in one of the disturbance scenarios, some of the attribute values were in conflict and that none of re-scheduling solution was dominating the others. This observation led to that the set of attributes needed to be narrowed down and internally prioritized. Based on the experimental results and the analysis of what the research community and the main stakeholder (i.e. Trafikverket) consider are the most important attributes in this context, the final set of attributes to use includes average final delay, maximum delay of a single train, total number of delayed trains and robustness. The contribution of this thesis is primarily the review and analysis of what attributes to use when performing a benchmark of re-scheduling solutions in real-time train traffic disturbance management. Furthermore, this thesis also contributes by performing an experimental assessment of how the attributes and their formulas could work in a pair-wise, quantitative benchmark for a set of disturbance scenarios and which issues that may occur due to conflicting objectives and attribute values. Concerning the enhancement of the visual tool and the visualization of the re-scheduling solutions, the experimental evaluation and analysis shows that the tool would not fit directly to the needs of the train dispatchers. This work should therefore only be seen as a starting point for the researchers whom are working with the development of decision support systems in this context. Furthermore, several iterative experiments have been conducted to select the appropriate attributes for benchmarking solutions and suggesting the best re-scheduling solution. During the experiments, we have used a limited set of different problem instances (2+2+7) representing three different types of disturbances. The performance of the enhanced visual tool EOT GUI+ and its functionalities should ideally also be analyzed further and improved by experimenting with a larger number of instances, for other parts of the Swedish railway network and in co-operation with the real users, i.e. the dispatchers.

Mestrado em Decisão Económica e Empresarial<br>Numa equipa de atendimento permanente com um escalonamento pré-definido, qualquer motivo de ausência de um colaborador (baixa, formação, férias, etc.) provoca uma cadeia de alterações nos horários já atribuídos. Atualmente, a forma de ultrapassar o problema consiste em afetar um elemento da equipa à árdua tarefa de realocar os colaboradores aos horários ainda não atribuídos, de forma manual. Este projeto pretende ultrapassar o problema através do desenvolvimento de uma heurística de reescalonamento que produza uma nova programação de horários. Inicialmente recorre-se ao VBA para reproduzir o escalonamento pré-definido pela empresa. Após o escalonamento, é programada uma heurística com o objetivo de minimizar o impacto no escalonamento inicial face a imprevistos. O resultado consiste num novo escalonamento tendo em conta restrições associadas a horários imprescindíveis e às limitações inerentes aos contratos laborais de cada colaborador.<br>In a permanent attendance team with a predefined schedule, any reason of absence given by an employee (illness, professional qualification, vacation, etc.) causes a chain of changes in the schedules already assigned. Now, the way to overcome the problem is to entrust a team member the arduous task of relocating employees to schedules not assigned yet, has to be done manually. This project aims to overcome the problem by developing a rescheduling heuristic that produces a new shifting plan. Initially, resorts to VBA which reproduce the default timetable of the company. After, is defined a heuristic in order to minimize the impact, in case of unexpected problems, in the initial stagger which will result in a new calendar, following all the restrictions associated with crucial schedules and inherent limitations in each employee's contract.

Master of Science<br>Department of Industrial and Manufacturing Systems Engineering<br>Todd W. Easton<br>Jessica L. Heier Stamm<br>Locomotives in the U.S. use over 3 billion gallons of fuel each year and faster refueling can increase rail network capacity without the infrastructure cost associated with new terminals or tracks. This thesis introduces the locomotive refueling system configuration problem (LRSCP), which seeks to improve efficiency in refueling yards through new technologies or policies. This research also creates two new methods to solve LRSCP. The first method uses an integer program to solve the off-line LRSCP and develop a static refueling policy. The train refueling integer program, TRIP, maximizes the weighted number of train combinations that can be refueled without delay. TRIP is optimized and its outputs are used as inputs to a simulation developed in Simio® for testing and validation. The second method creates an integrated integer program and simulation to solve the on-line LRSCP and produces a dynamic refueling policy. This tool, built in Python, incorporates a different integer program, the strike line integer program (SLIP), into the simulation. SLIP determines the optimal refueling assignment for each incoming train. The simulation incorporates SLIP’s solution for testing and validation. This tool is truly integrated and requires approximately 300 instances of SLIP to simulate a single day. Based on experimental results, solving either TRIP or SLIP and incorporating the optimal refueling policy improves railyard operations by 10 to 30%. This impact is statistically significant and increases the capacity of a railyard. Additionally, it impacts other important parameters such as time spent in the yard and the maximum queue for the railyard. Furthermore, there is a significant decrease in wasted time and an improvement to railyard efficiency. Implementing either method should increase a railyard’s capacity and significantly increase revenue opportunities.

The purpose with this report is to develop a network based insertion algorithm and evaluate it on a real-case timetable. The aim of the algorithm is to minimize the effect that that train implementation cause on the other, already scheduled traffic. We meet this purpose by choosing an objective function that maximizes the minimum distance to a conflicting train path. This ensures that the inserted train receives the best possible bottleneck robustness. We construct a graph problem, which solve with a modified version of Dijkstra’s algorithm. The complexity of the algorithm is Ο(s^2 t log⁡(s^2 t). We applied the algorithm on a Swedish timetable, containing 76 stations. The algorithm performs well and manage to obtain the optimal solution for a range of scenarios, which we have evaluated in various experiments. Increased congestion seemed to reduce the problem size. The case also show that a solution’s robustness decreases with increasing total number of departures. One disadvantage with the algorithm is that it cannot detect the best solution among those using the same bottleneck. We propose a solution to this that we hope can be implemented in further studies.

EMBA Project Report<br>EXECUTIVE SUMMARY: The objective of our project is to investigate current scheduling requirements, constraints, and procedures to identify problems with scheduling practices and syllabus management for Primary Flight Training in Training Wing 4. We analyzed three alternative scheduling approaches to reduce excess training time in the maximum efficient manner. Alternative 1: Prioritize students based on deviations from syllabus flow Changing the prioritization of students does not have a direct impact on reducing Training Timeline, since no additional production capacity is being added. However, changing the prioritization of scheduling students to give the highest priority to students who are the most behind should reduce gaps in training and increase proficiency, thereby reducing failures and required warm up flights for time out of the cockpit. This will reduce time-to-train (TTT) and additional overhead flights. The Training Timeline function of TIMS provides information on deviations from syllabus-designed TTT for use in the prioritization in scheduling. Alternative 2: Utilize aircraft availability in schedule builds Like instructors and students, aircraft are required to complete a flight event, and should be managed accordingly. Schedule writers can use current metrics of aircraft availability and make reasonable assumptions on the longevity of the information to predict follow-on production capacity. Events scheduled without considering aircraft availability should be presumed unlikely until availability is confirmed. Alternative 3: Monitor completer production / TTT deficits to trigger increased production When necessary, increased production can be gained through very limited means without introducing further scheduling constraints. Schedule writers must monitor when excess capacity is required and consider what can be gained at what cost; options can be prioritized based on a reasonable ordering (based on relative costs, both monetary and follow-on production loss risk) of the available options: Saturday operations, mandatory prepositions, forced cross countries, or recommending a detachment. We recommend TIMS Training Timeline function permissions be made available to schedule writing personnel for the operational database. Training needs to be provided to all TRAWING 4 schedule writers from the TIMS help desk to ensure utilization and integration of the Training Timeline. Scheduling in this manner will help ensure that extra syllabus flight requirements and time out of the cockpit are minimized. Scheduling templates based on aircraft availability will ensure events are planned to the maximum capacity of the system. We recommend schedule writers monitor Daily Status Reports and build follow-on schedules based on predicted asset availability. This will help avoid unnecessary use of other variables that could contribute to rippling production limitations. When it is mandatory to fly other than normal weekday field hours, having the field open for mandatory Saturday operations is the best alternative to gain on the student deficit depicted on the Training Timeline. Simultaneously, squadrons can use prepositions and cross countries to manage their own in house training deficits as they see fit.

Since the population growth of Stockholm Region is rapid, leading to larger demand on Public Transport and especially metro, four Municipalities of the Region have agreed on the expansion of the metro network. Blue metro line will be extended to Nacka and Hagsatra in the south and Barkarby in the north of the Swedish capital. The new railway line connections have been already planned, while the operation of the expanded line is analyzed in the current thesis. Taking the expected increase of passenger volumes and the operation of the current Blue line into account and following the safety restrictions, two alternative regular timetables of the expanded Blue line, limited to the morning rush service on a working weekday, have been constructed. The operation at stations of low expected passenger volume on the train is evaluated concerning the satisfaction of the operator. The rst alternative metro operation with trac every 4 minutes during the rush hour is concluded to be less ecient than the second alternative with 5 minutes headway, as 21 % larger amount of rolling stock is needed and more seats are not occupied. Finally, in order to achieve higher operational eciency at the low-demanded stations, a third Blue line operation, that is based on the second alternative and it includes short services, operating on a part of the line and not on the full-length of it, has been proposed. Although the number of trains needed for the morning peak hour operation remains constant between the second and third alternative operations, the proportion of empty seats at the analyzed stations is expected to be lower during the last alternative operation, resulting in a metro line scheduling that satises the operator most.

[EN] Many industrial problems can be modelled as a scheduling problem where some resources are assigned to tasks so as to minimize the completion time, to reduce the use of resources, idle time, etc. There are several scheduling problems which try to represent different kind of situations that can appear in real world problems. Job Shop Scheduling Problem (JSP) is the most used problem. In JSP there are different jobs, every job has different tasks and these tasks have to be executed by different machines. JSP can be extended to other problems in order to simulate more real problems. In this work we have used the problem job shop with operators JSO(n,p) where each task must also be assisted by one operator from a limited set of them. Additionally, we have extended the classical JSP to a job-shop scheduling problem where machines can consume different amounts of energy to process tasks at different rates (JSMS). In JSMS operation has to be executed by a machine that has the possibility to work at different speeds. Scheduling problems consider optimization indicators such as processing time, quality and cost. However, governments and companies are also interested in energy-consumption due to the rising demand and price of fuel, the reduction in energy commodity reserves and growing concern about global warming. In this thesis, we have developed new metaheuristic search techniques to model and solve the JSMS problem. Robustness is a common feature in real life problems. A system persists if it remains running and maintains his main features despite continuous perturbations, changes or incidences. We have developed a technique to solve the $JSO(n,p)$ problem with the aim of obtaining optimized and robust solutions. We have developed a dual model to relate optimality criteria with energy consumption and robustness/stability in the JSMS problem. This model is committed to protect dynamic tasks against further incidences in order to obtain robust and energy-aware solutions. The proposed dual model has been evaluated with a memetic algorithm to compare the behaviour against the original model. In the JSMS problem there are a relationship between Energy-efficiency, Robustness and Makespan. Therefore, the relationship between these three objectives is studied. Analytical formulas are proposed to analyse the relationship between these objectives. The results show the trade-off between makespan and robustness, and the direct relationship between robustness and energy-efficiency. To reduce the makespan and to process the tasks faster, energy consumption has to be increased. When the energy consumption is low it is because the machines are not working at highest speed. So, if an incidence appears, the speed of these machines can be increased in order to recover the time lost by the incidence. Hence robustness is directly related with energy consumption. Additionally, robustness is also directly related with makespan because, when makespan increases, there are more gaps in the solution, these incidences can be absorbed by these natural buffers. The combination of robustness and stability gives the proposal an added value due to since an incidence cannot be directly absorbed by the disrupted task and it can be repaired by involving only a small number of tasks. In this work we propose two different techniques to manage rescheduling over the JSMS problem. This work represents a breakthrough in the state of the art of scheduling problems and in particular the problem where energy consumption can be controlled by the rate of the machines.<br>[ES] Muchos de los problemas industriales se pueden modelar como un problema de scheduling donde algunos recursos son asignados a tareas a fin de minimizar el tiempo de finalización, para reducir el uso de los recursos, el tiempo de inactividad, etc. Job-Shop scheduling (JSP) es el problema más utilizado. En JSP hay diferentes trabajos, cada trabajo tiene diferentes tareas y estas tareas tienen que ser ejecutadas por diferentes máquinas. JSP puede ser extendido a otros problemas con el fin de simular una mayor cantidad de problemas reales. En este trabajo se ha utilizado el problema job shop scheduling con operadores JSO(n, p), donde cada tarea también debe ser asistida por un operador de un conjunto limitado de ellos. Además, hemos ampliado el clásico problema JSP a un problema donde las máquinas pueden consumir diferentes cantidades de energía al procesar tareas a diferentes velocidades (JSMS). En JSMS las operaciones tiene que ser ejecutadas por una máquina que tiene la posibilidad de trabajar a diferentes velocidades. Los problemas de scheduling consideran indicadores de optimización tales como: el procesamiento de tiempo, la calidad y el coste. Sin embargo, hoy en día los gobiernos y los empresarios están interesados también en el control del consumo de energía debido al aumento de la demanda y del precio de los combustibles, la reducción de las reservas de materias primas energéticas y la creciente preocupación por el calentamiento global. En esta tesis, hemos desarrollado nuevas técnicas de búsqueda metaheurística para modelar y resolver el problema JSMS. La robustez es una característica común en los problemas de la vida real. Un sistema persiste si permanece en funcionamiento y mantiene sus principales características a pesar de las perturbaciones continuas, cambios o incidencias. Hemos desarrollado una técnica para resolver el problema JSO(n, p) con el objetivo de obtener soluciones robustas y optimizadas. Hemos desarrollado un modelo dual para relacionar los criterios de optimalidad con el consumo de energía y la robustez/estabilidad en el problema JSMS. Este modelo se ha desarrollado para proteger a las tareas dinámicas contra incidencias, con el fin de obtener soluciones sólidas y que tengan en cuenta el consumo de la energía. El modelo dual propuesto ha sido evaluado con un algoritmo memético para comparar el comportamiento frente al modelo original. En el problema JSMS hay una relación entre la eficiencia energética, la robustez y el makespan. Por lo tanto, se estudia la relación entre estos tres objetivos. Se desarrollan fórmulas analíticas para representar la relación estimada entre estos objetivos. Los resultados muestran el equilibrio entre makespan y robustez, y la relación directa entre la robustez y eficiencia energética. Para reducir el makespan, el consumo de energía tiene que ser aumentado para poder procesar las tareas más rápido. Cuando el consumo de energía es bajo, debido a que las máquinas no están trabajando a la velocidad más alta, si una incidencia aparece, la velocidad de estas máquinas puede ser aumentada con el fin de recuperar el tiempo perdido por la incidencia. Por lo tanto la robustez está directamente relacionada con el consumo de energía. Además, la robustez también está directamente relacionada con el makespan porque, cuando el makespan aumenta hay más huecos en la solución, que en caso de surgir incidencias, estas pueden ser absorbidas por estos buffers naturales. La combinación de robustez y estabilidad da un valor añadido debido a que si una incidencia no puede ser absorbida directamente por la tarea interrumpida, esta puede ser reparada mediante la participación un pequeño número de tareas.En este trabajo se proponen dos técnicas diferentes para gestionar el rescheduling sobre el problema JSMS. Este trabajo representa un avance en el estado del arte en los problemas de scheduling y en el problema donde el consumo de energía p<br>[CAT] Molts dels problemes industrials es poden modelar com un problema de scheduling on alguns recursos són assignats a tasques a fi de minimitzar el temps de finalització, per a reduir l'ús dels recursos, el temps d'inactivitat, etc. Existeixen diversos tipus de problemes de scheduling que intenten representar diferents situacions que poden aparèixer en els problemes del món real. Job-Shop scheduling (JSP) és el problema més utilitzat. En JSP hi ha diferents treballs, cada treball té diferents tasques i aquestes tasques han de ser executades per diferents màquines. JSP pot ser estès a altres problemes amb la finalitat de simular una major quantitat de problemes reals. En aquest treball s'ha utilitzat el problema job shop scheduling amb operadors JSO(n, p), on cada tasca també ha de ser assistida per un operador d'un conjunt limitat d'ells. A més, hem ampliat el clàssic problema JSP a un problema on les màquines poden consumir diferents quantitats d'energia per a processar tasques a diferents velocitats (JSMS). Els problemes de scheduling consideren indicadors d'optimització tals com: el processament de temps, la qualitat i el cost. No obstant açò, avui en dia els governs i els empresaris estan interessats també amb el control del consum d'energia a causa de l'augment de la demanda i del preu dels combustibles, la reducció de les reserves de matèries primeres energètiques i la creixent preocupació per l'escalfament global. En aquesta tesi, hem desenvolupat noves tècniques de cerca metaheurística per a modelar i resoldre el problema JSMS. La robustesa és una característica comuna en els problemes de la vida real. Un sistema persisteix si continua en funcionament i manté les seues principals característiques malgrat les pertorbacions contínues, canvis o incidències. Hem desenvolupat una tècnica per a resoldre el problema JSO(n, p) amb l'objectiu d'obtenir solucions robustes i optimitzades. Hem desenvolupat un model dual per a relacionar els criteris de optimalidad amb el consum d'energia i la robustesa/estabilitat en el problema JSMS. Aquest model s'ha desenvolupat per a protegir a les tasques dinàmiques contra incidències, amb la finalitat d'obtenir solucions sòlides i que tinguen en compte el consum de l'energia. El model dual proposat ha sigut evaluat amb un algorisme memético per a comparar el comportament front un model original. En el problema JSMS hi ha una relació entre l'eficiència energètica, la robustesa i el makespan. Per tant, s'estudia la relació entre aquests tres objectius. Es desenvolupen fórmules analítiques per a representar la relació estimada entre aquests objectius. Els resultats mostren l'equilibri entre makespan i robustesa, i la relació directa entre la robustesa i l'eficiència energètica. Per a reduir el makespan, el consum d'energia ha de ser augmentat per a poder processar les tasques més ràpid. Quan el consum d'energia és baix, a causa que les màquines no estan treballant a la velocitat més alta, si una incidència apareix, la velocitat d'aquestes màquines pot ser augmentada amb la finalitat de recuperar el temps perdut per la incidència. Per tant la robustesa està directament relacionada amb el consum d'energia. A més, la robustesa també està directament relacionada amb el makespan perquè, quan el makespan augmenta hi ha més buits en la solució, que en cas de sorgir incidències, aquestes poden ser absorbides per els buffers naturals. La combinació de robustesa i estabilitat dóna un valor afegit a causa de que si una incidència no pot ser absorbida directament per la tasca interrompuda, aquesta pot ser reparada mitjançant la participació d'un xicotet nombre de tasques. En aquest treball es proposen dues tècniques diferents per a gestionar el rescheduling sobre el problema JSMS. Aquest treball representa un avanç en l'estat de l'art en els problemes de scheduling i, en particular, en el problema on el consum d'energia pot ser controlat per<br>Escamilla Fuster, J. (2016). Eficiencia Energética y Robustez en Problemas de Scheduling [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64062<br>TESIS

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.<br>Committee Chair: Al-Khayyal, Faiz; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Karimi, IA; Committee Member: Sokol, Joel.

Nesta tese, nós apresentamos uma compilação de três artigos de otimização aplicados no contexto de transporte urbano de ônibus. O principal objetivo foi estudar e implementar heurísticas com base em Pesquisa Operacional para otimizar problemas de (re)escalonamento de veículos off-line e on-line considerando várias garagens e frota heterogênea. No primeiro artigo, foi proposta uma abordagem heurística para o problema de escalonamento de veículos múltiplas garagens. Acreditamos que as principais contribuições são o método de geração de colunas para grandes instâncias e as técnicas de redução do espaço de estados para acelerar as soluções. No segundo artigo, adicionamos complexidade ao considerar a frota heterogênea, denotada como multiple depot vehicle type scheduling problem (MDVTSP). Embora a importância e a aplicabilidade do MDVTSP, formulações matemáticas e métodos de solução para isso ainda sejam relativamente inexplorados. A principal contribuição desse trabalho foi o método de geração de colunas para o problema com frota heterogênea, já que nenhuma outra proposta na literatura foi identificada no momento pelos autores. Na terceira parte desta tese, no entanto, nos concentramos no reescalonamento em tempo real para o caso de quebras definitivas de veículos. A principal contribuição é a abordagem eficiente do reescalonamento sob uma quebra. A abordagem com redução de espaço de estados, solução inicial e método de geração de colunas possibilitou uma ação realmente em tempo real. Em menos de cinco minutos, reescalonando todas as viagens restantes.<br>In this dissetation we presented a three articles compilation in urban bus transportation optimization. The main objective was to study and implement heuristic solutions method based on Operations Research to optimizing offline and online vehicle (re)scheduling problems considering multiple depots and heterogeneous fleet. In the first paper, a fast heuristic approach to deal with the multiple depot vehicle scheduling problem was proposed. We think the main contributions are the column generation framework for large instances and the state-space reduction techniques for accelerating the solutions. In the second paper, we added complexity when considering the heterogeneous fleet, denoted as "the multiple-depot vehicle-type scheduling problem" (MDVTSP). Although the MDVTSP importance and applicability, mathematical formulations and solution methods for it are still relatively unexplored. We think the main contribution is the column generation framework for instances with heterogeneous fleet since no other proposal in the literature has been identified at moment by the authors. In the third part of this dissertation, however, we focused on the real-time schedule recovery for the case of serious vehicle failures. Such vehicle breakdowns require that the remaining passengers from the disabled vehicle, and those expected to become part of the trip, to be picked up. In addition, since the disabled vehicle may have future trips assigned to it, the given schedule may be deteriorated to the extent where the fleet plan may need to be adjusted in real-time depending on the current state of what is certainly a dynamic system. Usually, without the help of a rescheduling algorithm, the dispatcher either cancels the trips that are initially scheduled to be implemented by the disabled vehicle (when there are upcoming future trips planned that could soon serve the expected demand for the canceled trips), or simply dispatches an available vehicle from a depot. In both cases, there may be considerable delays introduced. This manual approach may result in a poor solution. The implementation of new technologies (e.g., automatic vehicle locators, the global positioning system, geographical information systems, and wireless communication) in public transit systems makes it possible to implement real-time vehicle rescheduling algorithms at low cost. The main contribution is the efficient approach to rescheduling under a disruption. The approach with integrated state-space reduction, initial solution, and column generation framework enable a really real-time action. In less than five minutes rescheduling all trips remaining.

Providing advanced health care at home rather than in a hospital creates a greater quality of life for patients and their families. It also lowers the risk of hospital-acquired infections and accelerates recovery. The overall cost of care per patient is decreased. Manual scheduling of patient visits by health care professionals (HCPs) has become a bottleneck for increased patient capacity at SABH, a ward providing advanced pediatric health care at home (“Sjukhusansluten Avancerad Barnsjukvård i Hemmet” in Swedish), since many parameters need to be taken into account during scheduling. This thesis aims to increase the efficiency of SABH’s daily scheduling of personnel and resources by designing an automated scheduler that constructs a daily schedule and incorporates changes in it when needed in order to remove scheduling as a limitation for increased patient capacity. Requirements on a feasible schedule are identified in cooperation with SABH and literature is investigated about similar areas where the scheduling process has been automated. The scheduling is formulated as a computerized problem and investigated from the perspective of theoretical computer science. We show that the scheduling problem is NP-hard and can therefore not be expected to be solved optimally. The algorithm for scheduling the visits minimizes violations of time windows and travel times, and maximizes person continuity and workload balancing. The algorithm constructs an initial solution that fulfills time constraints using a greedy approach and then uses local search, simulated annealing, and tabu search to iteratively improve the solution. We present an exact rescheduling algorithm that incorporates additional visits after the original schedule has been set. The scheduling algorithm was implemented and tested on real data from SABH. Although we found the algorithm to be efficient, automatic transfer of data from the patient journal system is an imperative for the scheduler to be adopted.<br>Barn som får avancerad sjukvård hemma istället för på sjukhus tillfrisknar ofta snabbare och risken för vårdrelaterade infektioner minskar. Barnen och deras familjer blir mer välmående av att få vistas i sin hemmiljö. På Astrid Lingrens barnsjukhus i Stockholm erbjuds avancerad hemsjukvård av avdelningen Sjukhusansluten Avancerad Barnsjukvård i Hemmet (SABH). För att schemalägga när patienterna ska besökas av sjukvårdspersonalen behöver många olika faktorer beaktas, detta sker idag helt manuellt. Den manuella schemaläggningen utgör en naturlig begränsning av SABHs patientkapacitet. Denna uppsats syftar till att effektivisera schemaläggningsprocessen hos SABH genom att föreslå en automatiserad lösning som hanterar koordinering av personal och resurser och dem förändringar som behöver göras i schemat under dagen, för att få bort schemaläggningsprocessen som ett hinder mot ökad patientkapacitet. Krav på schemaläggningen identifieras i diskussion med SABH och genom att studera litteratur kring liknande områden där schemaläggning lösts automatiserat. Vi formulerar schemaläggningen som ett datologiskt problem och analyserar det med utgångspunkt i teoretisk datalogi. Vi visar att problemet är NP-svårt och därför inte kan förväntas lösas optimalt inom rimlig tid. Vår lösning approximerar istället fram ett rimligt svar, där fokus hos algoritmen är att patienterna ska besökas de tider de behöver, personalens restider ska vara så korta som möjligt samtidigt som arbetsbördan hos personalen ska vara så lika fördelad som möjligt och patienterna ska, i den mån det är möjligt, få vård av samma personal. Med en girig algoritm konstrueras ett initialt schema som uppfyller de grundläggande kraven, detta schema förbättras med lokalsökning, simulated annealing och tabusökning. En exakt lösning framställs för uppdatering av schemat. Algoritmen för att lägga ett dagligt schema (utan uppdateringar) implementerades och testades med riktigt data från SABH. Vår algoritm visade sig vara effektiv, men för att kunna göra hela schemaläggningsprocessen effektiv behöver den integreras med journalsystemet.

Mestrado em Métodos Quantitativos para a Decisão Económica e Empresarial<br>O objetivo deste projeto é resolver um problema de reescalonamento de bombeiros voluntários, recorrendo a técnicas de investigação operacional. O problema em causa consiste em fazer uma nova escala quando se é deparado com uma ou mais ausências inesperadas, tendo sempre como base a disponibilidade apresentada mensalmente pelos bombeiros, bem como a escala inicial. O problema foi formulado em programação linear inteira, tendo sido resolvido computacionalmente com recurso ao OpenSolver. Foram desenvolvidos dois modelos de reescalonamento, com dois objetivos diferenciados. O primeiro consiste em obter um novo escalonamento tendo em conta as restrições e não alterando turnos afetados no plano inicial, além dos decorrentes das faltas identificadas. No segundo modelo é permitido fazer alterações ao plano inicial sendo que o objetivo é minimizar as diferenças entre as duas escalas, a inicial e a resultante do reescalonamento. Da resolução de cada modelo obtém-se um novo plano de escalonamento final que cubra as ausências não programadas, sem intervenção humana. Assim, com recurso ao OpenSolver, é possível dispor de uma solução num curto espaço de tempo computacional. O modelo permite ainda testar, em pouco tempo, diferentes alternativas.<br>The objective of this project is to solve the rescheduling problem of voluntary firefighters, while using operational research techniques. The problem involves creating a new schedule (scale) when faced with one or more unexpected absences, based on the availability presented monthly by each firefighter as well as on the initial scale. The problem was formulated in integer linear programming and was solved computationally using OpenSolver. Two rescheduling models were developed, with two different objectives. The first one aims to create a new schedule that takes into account all the restrictions, without changing the assignments of the initial plan, except those due to absences. In the second model, some changes were made to the initial plan. This time, the objective is to minimize the differences between the two schedules, the initial schedule and the final rescheduling. The results of these two models devise a new final scheduling plan that covers the non- programmed absences, without human intervention and obtained through OpenSolver, that grants a solution in a short computational time. The model also allows to test, in a short time, different alternatives.<br>info:eu-repo/semantics/publishedVersion

Railway transportation has great potential, but interdependencies in the railway traffic make trains very sensitive to disturbances, which can bedifficult to handle. Using railway in an intermodal transport chain may complicate the interconnections with other modes if there is large uncertainty in the performance of the railway. A study based on interviews with several customers of the Swedish National Railway Administration shows that the customers lack information regarding occurrences of disturbances and the consequences for their trains, i.e. the new estimated time of arrival. This information is necessary when taking actions within the customers’ organisation to minimise the negative impacts. Predicting the consequences of a disturbance and the effects of counter measures taken by the Swedish train traffic managers is today an overwhelming task considering there is no computational decision support available. However, provided that the traffic and decision-making could be simulated, the effects from disturbances and actions taken could be computed. Requirements regarding computational time for a simulation are obviously significant and affect the usefulness in a real-time environment. For strategic purposes, a simulator could also serve as an analytical tool for evaluating strategies for handling certain types of disturbances. An approach to model the different layers of such a simulator, taken into account the infrastructure, the traffic flow and the influence of the traffic management decisions and transport operators, is presented. The part that covers the interaction between train traffic and infrastructure has been implemented as a small-scale discrete-event simulator. The simulator is extended by an optimisation approach, attempting to act as decision support for the train traffic managers when handling disturbances by generating effective counter measures. It is composed by a linear model specifying the timetable of a sub-network and solved by optimisation software. Iteratively, a heuristic is applied to modify the timetable by changing meets and overtakes and generate a new updated linear model to be solved. In addition to consider the train traffic system as an explicit part of a transport chain, it can be seen as a black box where some relations between input and output are known. We have investigated how uncertainty in the reliability related to one or several transport links can be handled when combining several links into a transport chain. A simulation-based approach is proposed.

Orientador: Fernando Antonio Campos Gomide<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação<br>Made available in DSpace on 2018-08-05T20:02:48Z (GMT). No. of bitstreams: 1 MotaFilho_FranciscoOsvaldoMendes_M.pdf: 2700152 bytes, checksum: 3ab58e91f1a3839dae9d39e47d33ff50 (MD5) Previous issue date: 2005<br>Resumo: Para obter uma solução satisfatória, algoritmos genéticos avaliam, em geral, um número grande de indivíduos durante o processo evolutivo. É comum, em aplicações práticas, encontrar funções de avaliação computacionalmente complexas e caras. Porém, nesses casos, o tempo é um fator determinante no desempenho de algoritmos genéticos. Dessa forma, os algoritmos genéticos devem encontrar soluções adequadas em curto intervalo de tempo. Uma alternativa promissora para contornar os custos computacionais referentes à função de avaliação considera o fato de que pode ser mais atrativo avaliar diretamente somente indivíduos selecionados e estimar os fitness dos restantes do que avaliar diretamente toda a população. Este trabalho propõe o uso de modelos de estimação de fitness em algoritmos genéticos. Especificamente, são sugeridos modelos de estimação baseados em agrupamento nebuloso supervisionado (Fuzzy C-Means) e não supervisionado (Aprendizagem Participativa). O objetivo é aproximar as funções de avaliação por meio de modelos de estimação de fitness, sem afetar significativamente a qualidade das soluções. Inicialmente, os modelos de estimação propostos são comparados e analisados experimentalmente com alternativas sugeri das por outros autores, utilizando, para isso, problemas de otimização considerados na literatura de algoritmos genéticos. A seguir, os modelos de estimação de fitness são aplicados em um problema real de engenharia, o planejamento de circulação de trens em ferrovias. Este é um caso típico onde o desempenho de cada planejamento exige um tempo significativo. A eficiência dos modelos propostos é verificada e comprovada experimentalmente comparando com os resultados, em instâncias mais simples, fornecidos por modelos de programação matemática e, em instâncias complexas, fornecidos pelo algoritmo genético clássico<br>Abstract: Genetic algorithms usually need a large number of fitness evaluations before a satisfying result can be obtained. In many real-world applications, fitness evaluation may be computationally complex and costly. In these cases, time is an essential subject in performance analysis of genetic algorithms. Therefore, genetic algorithms should provide good solutions in a short period of time. A promising approach to alleviate the computational cost of evaluations considers the fact that sometimes it is better to evaluate only selected individuals and estimate the fitness of the remaining individuals instead of evaluate a whole population. This work suggests the application of fitness estimation models in genetic algorithms. More specifically, it deals with estimation models based on supervised fuzzy clustering (Fuzzy C-Means) and unsupervised fuzzy clustering (Participatory Learning). The goal is to approximate the evaluation functions through the use of fitness estimation models, without significantly affect the quality of solutions. Initially, the fitness estimation models are compared and analyzed experimentally with other models already proposed in the literature. Their performance are evaluated using benchmark optimization problems found in the genetic algorithms literature. Next, the fitness estimation models are used to solve a real-world engineering problem, namely the train scheduling in a freight rail line. This is a typical case where the performance measure of each schedule demands a considerable amount of time. Once again, the performance of the fitness estimation models are evaluated experimentally, comparing their results with the results provided, for simple instances, by linear programming models and, for complex instances, by the classic genetic algorithm<br>Mestrado<br>Engenharia de Computação<br>Mestre em Engenharia Elétrica

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-10-31T20:55:43Z No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5)<br>Made available in DSpace on 2017-10-31T20:55:43Z (GMT). No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) Previous issue date: 2017-07-19<br>Freight railways are the major means of transportation of bulk material, such as iron ore from the origin to the destination. Usually for heavy haul railways, the destination is a port. For the last few years there has been a fast growing demand. However, railway infrastructure capacity increasing is very expensive and require a lot of investiment budget. Therefore, an improvement of train scheduling process is needed to ensure the best and efficient use of the current railway. Nevertheless, in some situations it is overwhelmingly complex to solve, an NP-hard problem. Since all the previous work provided on the Train Timetable Problem is usually only applied locally to a single railway, this work provides a public base benchmark of test railways built by heuristcs. Moreover, this work deals with the train timetabling problem applied to mixed traffic railways with both cargo trains and passenger trains sharing the same resources with different priorities. It is proposed a new mathematical model extended from literature previous work intended to avoid infeasible solutions instead reparing or discarding on these cases. This model contains additional support for parallel multi-track for several railway’s signaling system approaches context as well as overtaking on it without deadlocks possibility. This model considers trains in current position and future departure planned. To achieve an improved train scheduling is applied the Evolutionary Clustering Search (ECS) with multi heuristics approaches and a modified mutation operator of Genetic Algorithm as component of ECS. The experiments shows ECS outperforms almost all tests scenario and the modified mutation operator strongly improve the results<br>Ferrovias de trens de carga são os principais meios de transporte de materiais, tais como minério de ferro, da sua origem até o seu destino. Geralmente para ferrovias de transporte pesado, o destino é o porto. Nos últimos anos, a demanda de produção tem aumentado assim como o uso da ferrovia para transportá-la, no entanto, a expansão da sua infraestrutura requer um grande investimento. Assim, um planejamento de circulação de trens mais efetivo que maximize a capacidade de tráfego se faz necessária. No entanto, em algumas situações a sua otimização é bastante complexa para ser executada, um problema NP-Difícil. Embora todo trabalho elaborado nesse tema é geralmente aplicado localmente em uma única ferrovia, este trabalho provê uma base genérica de ferrovias gerado por heurísticas. Além disso, esta dissertação lida com o problema de circulação de trens aplicado a ferrovias mistas envolvendo trens de carga assim como trens de passageiros compartilhando o mesmo recurso e com diferentes prioridades. É proposto um novo modelo matemático estendido de um trabalho existente na literatura que procura evitar conflitos ao invés de permitir soluções inviáveis, sendo necessário reparação delas ou descarte. Este modelo lida com uma quantidade variável de linhas em locais de parada compatível com várias abordagens de sistema de sinalização disponíveis, assim como considera ultrapassagens de forma a evitar deadlocks, da mesma forma que trata contextos de trens em circulação como planejados para realizar a otimização. Para encontrar boas soluções, ao planejamento de circulação de trens é aplicado uma abordagem do Evolutionary Clustering Search (ECS) com múltiplas heurísticas, e um operador de mutação modificado do Algoritmo Genético como componente do ECS. Os experimentos computacionais mostraram que o ECS superou quase todos os cenários de teste e o operador de mutação modificado melhorou significativamente os resultados finais.

La régulation ferroviaire sur de vastes zones est un problème complexe. Elle intervient dans la phase opérationnelle de la production. Son rôle consiste à trouver de nouvelles solutions en termes de planification des mouvements de trains suite à l'apparition d'un incident empêchant la réalisation normale du plan de transport préétabli dans les phases amont de la production.La contribution de ce travail s'organise autour de trois axes.Le premier consiste à définir une formalisation exhaustive du système ferroviaire, associé à une représentation plus cohérente (modèle multiniveau).Le deuxième axe s'articule autour de l'étude des modèles mathématiques pour la régulation du trafic ferroviaire: évolutions d'un modèle en temps continu complet (espacements dynamiques), proposition d'un modèle innovant à temps discret et d'un modèle mixte (continu-discret) adossé au modèle multiniveau.Enfin, le dernier axe traite de la mise en oeuvre concrète au niveau industriel, en particulier des gains attendus du couplage avec un outil de simulation<br>On-line re-scheduling of trains aims to find accurate solutions after an incident has occurred on the railway network. When we consider a large area, solutions consist in calculating new timetables, sequences and routes of trains. This problem asks for decision support tools based on operational research techniques.This thesis aims to develop solutions toward an operational tool, it articulates around three main parts. The first part defines an exhaustive model of the railway system operations and a multiscalable description of the infrastructure.The second part presents three mathematical models of the rescheduling problem associated with this description. We preset a exhaustive continuous time based model including headways that take into account speeds of trains, plus a discrete time based model and an hybrid model combining both formulations.The last part describes first implementations and the global framework we need to develop in order to solve the real world problem. It emphases on expected synergies, specilaly between simulation and optimization techniques

Dans l'exploitation ferroviaire en zone dense, des incidents mineurs peuvent rapidement entraîner des retards. Ces retards peuvent ensuite rapidement se propager et s'amplifier le long d'une ligne, voire d’autres lignes qui partagent l'infrastructure, le matériel roulant ou les conducteurs. Cette thèse considère le problème de prise de décisions en temps réel lors de la gestion opérationnelle d'un système ferroviaire dense. Le fonctionnement de l'exploitation en zone dense et ses points de fragilités sont d’abord exposés. Nous proposons une caractérisation de la notion de stabilité d'un système ferroviaire dense. Le problème de replanification considéré est introduit et positionné par rapport aux différents travaux existants dans la littérature en transport ferroviaire et en transport urbain. Une première approche de résolution par programmation linéaire en nombres entiers est proposée, elle permet d'établir la pertinence de la replanification en temps réel. Une seconde approche itérative, plus complète, est ensuite présentée. Cette approche est basée sur un couplage optimisation-simulation. Elle permet d'inclure toutes les décisions opérationnelles utilisées par les agents opérationnels, d'évaluer finement l'impact de ces décisions pour les voyageurs et de proposer différentes solutions grâce à une résolution multi-objectif. Un prototype d’un outil de replanification basé sur l'approche itérative a été développé et branché aux flux de données industriels. Des expérimentations en environnement réel sur une ligne Transilien ont permis de valider que l’outil, et par conséquent l’approche, répond aux attentes des acteurs opérationnels<br>While operating a dense railway system, minor incidents can easily generate delays. Those delays can spread and rapidly amplify along one line, and sometimes to other lines sharing the infrastructure, rolling-stock units or drivers. This thesis addresses the real-time decision-making problem while operating a dense railway system. Dense railway operations are first presented, along with their properties and weaknesses. The notion of stability for a dense railway system is introduced and discussed. Related problems and approaches of the literature are reviewed, both in railway and in urban transportation, and the considered real-time rescheduling problem is presented. A first resolution approach, based on an Integer Linear Programming model, is proposed, and numerical experiments on real data are analyzed. They show the relevance of the rescheduling problem. A more general approach is then proposed, that iterates between an optimization module and a simulation module. All operational actions are considered in the iterative approach, and the use of simulation allows for a precise evaluation of the impact of actions on passengers. This new approach is also multi-objective, thus different solutions can be proposed to the decision makers. A rescheduling tool has been implemented, using the iterative approach, and connected to industrial data flows. Real-life experiments on a Transilien line proved that the tool, and thus the iterative approach, fulfills the decision makers’ expectations and helps reducing the duration of perturbations and their impact on passengers

碩士<br>國立高雄第一科技大學<br>資訊管理所<br>90<br>In the era of E-commerce, due to the global competition and rapid changes of markets, the management of manufacturing industries is much more complicated than before. Some distinct features of the present market environment are: shorter product-life, shorter production lead time, and smaller batches of production. The later demand has exerted great pressures on management for greater flexibility in production scheduling, which must meet the customer needs of rapid changing nature. Rescheduling is thus becoming an indispensable capability for modern production management, where activities of a production schedule, before it is completed, must be re-arranged due to requests of cancellation of orders, additions of urging orders, and/or changes of specifications of an existing order. Rescheduling in the past was usually done manually, which requires expertise of experienced workers who, based on the previous cases, adjust activities and/or processes. However, the lack of systematic and optimal analysis is always an inherent problem of the solution approach that is based on personal experience. As a result, performance of production scheduling may not be efficient, and management may find it difficult to integrate the adjusted production scheduling into eBusiness system easily. Many manufacturing industries in Taiwan, who have no capability in systematic rescheduling, thus cannot predict exact due day for customers. The purpose of this research is to attempt to tackle the rescheduling problem by developing a systematic rescheduling framework for manufacturing industries. We applied CSP (constraint satisfaction problem) as the solution tool to develop a CSP based scheduling and rescheduling framework for manufacturing industries. In the framework, scheduling or rescheduling problem is represented as a CSP model, which consists of processes for handling scheduling interruption events, including rush orders or order withdraws, work order changes, equipment breakdowns and due day changes. The model works in concert with CSP method such as Search Algorithms, Constraint Propagation and Variable/Value Ordering. The framework was applied to a simplified manufacturing environment of a notebook computer factory in southern Taiwan. We, based on the framework, develop a system using constraint programming tools ILOG Solver and Scheduler. The system is able to handle the scheduling interruption events efficiently and effectively. We also conducted experiments with two rescheduling methods, schedule-or-postponed with objective function of minimize-changes and depth-first backtracking search with objective function of minimize-makespan, and compared their results.

碩士<br>逢甲大學<br>工業工程與系統管理學研究所<br>99<br>Production scheduling issues are central to manufacturing. Resource allocation decisions made in the production plan have far-reaching effects on machine utilization levels, order completion times, and overall factory efficiency. Traditional scheduling approaches must be updated to meet the needs of the present day; in particular, schedules must not result in large inventories and long machine idle times. Some scheduling approaches that were effective for mass production in the 20th century are no longer useful for 21st century manufacturing. Job shop production is an NP-hard scheduling problem with numerous applications. Dynamic job arrival complicates the job shop problem. In 1992, Dorigo et al. proposed Ant Colony Optimization (ACO), which has been very useful for many NP-hard problems. ACO can generate schedules for the job shop problem. The proposed research examines four rescheduling methods, all of which apply ACO to job shop problems with dynamic job arrival. This study demonstrated that the different performance indicators, the process according to the number of process and processing time range, the way for the adjoining of the schedule will be different: performance indicators - total completion time, new orders immediately rescheduling type in different number of process and processing time have a stable good performance. Performance indicators - the mean flow time, the traditional cycle rescheduling type in the number of process and processing time vary the range of the more balanced would be a good performance. Cycle & plug rescheduling in the number of processes and processing time are fixed have a good performance. In the event-driven rescheduling:in the new orders immediately rescheduling type , greater the number of processing and processing time range, this rescheduling will have a better performance. Most of the research proposed scheduling interface methods, can produce in seconds a new schedule means that in the future to the industry there is a certain level of practicality.

碩士<br>逢甲大學<br>工業工程與系統管理學研究所<br>97<br>In 2007, the world began a notable economic recession that caused shortages of orders for goods and products. This lack of orders forces factories to seek drastic methods to maintain their profit margins, such as employee layoffs, wage reductions, unpaid leaves, and so on. It is essential to reduce capitalized costs, to shorten the hours required to finish projects, to deliver products to customers as soon as possible while retaining service quality for valuable, long-term clients. This essay deals with job shop environments. To maintain a definite level of manufacturing efficiency, a shop must reschedule at appropriate times. This research develops a scheduling system in the context of periodic rescheduling. This research evaluates the two scales of visibility for the calculating core of an Ant Colony System (ACS) used for periodic rescheduling. Shortest Processing Time (SPT) and Most Work Remaining (MWKR) are compared and MWKR is shown to be the best for this particular formulation. This research shows that a prior job insertion system can use available machine idle time. This prior job insertion method uses MWKR to insert new orders into available machine idle time. Further, the research describes a priority liberation software mechanism that improves the efficiency of periodic rescheduling. Four scheduling schemes are compared: periodic scheduling using MWKR visibility in the ACS, dynamic scheduling in the ACS, the prior job insertion system, and dispatching rules. This comparison shows that the prior job insertion system produces schedules with the shortest makespans. The comparison shows that the choice between MWKR and SPT can directly affect the efficiency of rescheduling. The final result is superior to previously reported dynamic rescheduling results.

碩士<br>樹德科技大學<br>經營管理研究所<br>94<br>At the trend of technology application and internationalization, in recent years, machinery industrial structure has been changing, and the management of enterprise is much more complicated than ever before. In the past, the style of mass production has been changed to customization and greater flexibility in production. And in all of the departments or functions in a factory management, production scheduling and management has faced direct impacts most. A good production scheduling and management is the key point of a factory ability to deal with emergent or competitive environment. The purpose of production scheduling is to plan on going production activities to be done more efficiently. However, planned schedule has always to be altered because of the join rush orders. When facing decision of rush orders rescheduling, if enterprise can reduce rescheduling variation range and narrow rescheduling time scope based on allowing costs, the impact to production line and enterprise will be significantly reduced. In machinery industrial, patching rule for earliest due date was scheduled by forward PERT concept. If schedule result was being changed, that caused material vary uncertainly and impacted production scheduling and management, while facing reschedule of rush orders rescheduling. The research is focused on machinery manufacturing, developing a production scheduling models and employing the meta-heuristic method based on constraint programming is adopted. The goal of the models is to satisfy customers demand and to minimize perturbation, minimizing inventory cost, minimizing time difference of end products to be finished and expected finished as the performance criteria. It shall provide an effective decision support system for the managers of the production planning system in machinery industry, increasing enterprise competitiveness further The entire experiment is performed using F Company, and provides enterprise management production planning to verify the meta-heuristic system which helps solving problems in practice.

The development of wide-area networks and the availability of powerful computers as low-cost commodity components are changing the face of computation. These progresses in technology make it possible to utilize geographically distributed resources in multiple owner domains to solve large-scale problems in science, engineering and commerce. Research on this topic has led to the emergence of Grid computing. To achieve the promising potentials of tremendous distributed resources in the Grid, effective and efficient scheduling algorithms are fundamentally important. However, scheduling problems are well known for their intractability, and many of instances are in fact NP-Complete. The situation becomes even more challenging in the Grid circumstances due to some unique characteristics of the Grid. Scheduling algorithms in traditional parallel and distributed systems, which usually run on homogeneous and dedicated resources, cannot work well in the new environments. This work focuses on workflow scheduling algorithms in the Grid scenario. New challenges are discussed, previous research in this realm is surveyed, and novel heuristic algorithms addressing the challenges are proposed and tested. The proposed algorithms contribute to the literature by taking the following factors into account when a schedule for a DAG-based workflow is produced: predictable performance fluctuation and non-deterministic performance model of Grid resources, the computation and data staging co-scheduling, the clustering characteristic of Grid resource distribution, and the ability to reschedule according to performance change after the initial schedule is made. The performance of proposed algorithms are tested and analyzed by simulation under different workflow and resource configurations.<br>Thesis (Ph.D, Computing) -- Queen's University, 2009-04-23 22:30:09.646

碩士<br>國立雲林科技大學<br>營建工程系碩士班<br>92<br>Construction project scheduling always plays an important rule leading to construction project success. From the contractor’s point of view, a practical schedule based on engineering experience is not only beneficial to the accuracy of project estimated duration and cost in bidding process, but the smooth operation while projects proceed. The proposed research adopts Constraint Programming techniques to resolve resource-constrained project scheduling issues. A new scheduling minimized total cost optimization model considering resource usage and idle cost, project indirect cost, penalty and bonus, is proposed. A new idea in recourse-constrained project scheduling, the concept of outsourcing resources is introduced in order to enhance the model feasibility on real construction scheduling problems. The importance of outsourcing resources through case discussion then recognized, based on the research result. Then the proposed research intends to discuss the topics of resource-constrained construction rescheduling, by applying the concepts of manufacturing rescheduling. Under the unique circumstances of construction industry, a new rescheduling mechanism is developed to investigate the influence factors of construction project rescheduling, and their impacts on initial schedules, with the objective of the minimum of overall fluctuation for all activities. Finally, a project scheduling and rescheduling optimization engine coded in C++ is developed to validate model feasibility and accuracy.

The goal of this thesis was to design and implement a graphical tool for visualization and editing of schedules which would provide a function for automatic repairing of violated constraints in the schedule. The resulting application called a Gantt Viewer is integrated to the FlowOpt project that represents a complex solution for modeling workflows, creation of schedules from them and analysis of these schedules. The application has been developed with the focus on intuitiveness of the user interface and performance during the management of large schedules. It enables the user to visualize extended manufacturing schedules thanks to the cooperation with other modules of the FlowOpt project. Moreover, the Gantt Viewer incorporates a repair tool exploiting a new Repair-DTP algorithm which is both introduced and demonstrated in this work.

No<br>In many production processes real time information may be obtained from process control computers and other monitoring systems, but most existing scheduling models are unable to use this information to effectively influence scheduling decisions in real time. In this paper we develop a general framework for using real time information to improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a strategy for using real time information for a single machine scheduling model and discuss how it may be used to incorporate real time information into scheduling the complex production processes of steel continuous caster planning.

碩士<br>國立高雄第一科技大學<br>運籌管理所<br>99<br>Abstract Although there are mutual influence between train driver scheduling problem and vehicle scheduling problem, but these problems are usually solved respectively. Driver scheduling problem has been there for a long time. One of the examples include: TRA drivers members, aircraft crew members and transportation drivers. The main consideration for the driver scheduling problem, how to use the limited manpower and cost, make the best scheduling job. Working class generation is the most time-consuming stage in the solving process of driver scheduling problems faced by large transportation companies such as TRA, Kaohsiung MRT and Taipei MRT. The object of this study is "case of TRA", the purpose for the train driver&apos;&apos;s scheduling problem. Through genetic algorithms, with the established scheduling constraints, to construct the train driver scheduling the feasible solutions. Objective is minimization of the number of train drivers (ie, the least number of working class), means to find a better work schedule, so the actual number of drivers at least, to build an effective solution. Because this study is a separate study, so the constraints under consideration didn&apos;&apos;t complete all of the specifications covering the TRA, but only to take some of the more important restrictions, including: 1. For example, the scope of Kaohsiung TRA, the duties are divided into Tze- Chiang, Fu-Hsing, Chu-Kuang and Local Express, a total of four vehicle type for scheduling. 2. Duty travel time to the day duty-based, which means this time 06:00 ~ 22:00. 3. The train driver scheduling in two modes: to allow drivers to travel across the vehicle types, and are not allowed. 4. Each individual vehicle type into a maximum of K drivers, and doesn&apos;&apos;t consider the shift issue. Finally, the work schedules of TRA Kaohsiung-B group (2010) as an example, refer to the same scheduling information, to find a better work schedule, so the actual number of drivers at least. From the results, the number of drivers can be reduced to 23 from 26.