1,721,031 research outputs found
Robust scheduling in an uncertain environment
No full textThis thesis presents research on scheduling in an uncertain environment, which forms a part of the rolling stock life cycle logistics applied research and development program funded by Dutch railway industry companies. The focus therefore lies on scheduling of maintenance operations on rolling stock in the railway industry. The first chapter describes some of the history of the Dutch railways, focusing on the rolling stock used, and it introduces the context in which NedTrain, a major Dutch rolling stock maintenance company, operates. While maintenance of rolling stock is not a new problem, recent changes in the field are identified in this chapter which introduce new challenges: the first is the declining involvement of maintenance experts in the procurement of new rolling stock, the second is the on-going demand for increasing efficiency. Based on this discussion, the goal of this thesis is to devise a method with which schedules can be created based on a flexible process. The schedules resulting from this method are to be both flexible, meaning that they can be adapted easily, and robust, meaning that they are resilient to the effects of uncertain events. Lastly, our goal is to create the schedules in such a way that the effects of disturbances in one team have little or no effect on any other teams in the same workshop. Chapter 2 examines existing research in the context of the formulated research goals. It is shown that the well-known Resource-Constrained Project Scheduling Problem (RCPSP) can be mapped to the problem of scheduling maintenance tasks on trains in the NedTrain workshops. The most important methods to solve the RCPSP are discussed, among which are many exact methods. Both the scale of the problem and the requirement of having a flexible schedule instead of a fixed time assignment for the tasks prohibit using these methods. Among the heuristic methods discussed, the Precedence Constraint Posting method turns out to be an especially good fit: it is able to solve large-sized problems very quickly, and it uses a Simple Temporal Network (STN) as a way of representing many different solutions to the original problem, offering a lot of flexibility. Based on the research discussed, research questions are formulated to answer the research goals. - The first question asks how to define criteria encapsulating the notion of flexibility as posed by our research goals, and how to measure the flexibility of a schedule. - The second question asks how we can make the best use of available flexibility to attain robustness. - The third question asks if there is also a way to extend the concept of temporal flexibility to include a form of sequential flexibility. - The last question asks how we can use our work on robustness to decouple schedules, ensuring that disturbances in the schedule for one agent have no impact on any other agents. The third chapter investigates criteria corresponding to our intuitive notion of flexibility in scheduling. The concept of interval schedules serves as a basis for this investigation: the idea is that each task in the schedule is assigned an interval from which its start time can be picked, and the length of all these intervals serves as a representation for the flexibility of the schedule. We show that flexibility measures in existing research lead to an over-estimation of the total available flexibility, because dependencies between tasks are not taken into account properly: simply adding the interval sizes for two dependent tasks causes over-estimation, because the picked time for one task can reduce the interval size for another task. Our first major contribution is an independence requirement for the creation of these intervals: we state that intervals should be constructed in such a way that any choice in one interval has no impact on the available choices in any of the other intervals. Our second major contribution is a method to actually construct such intervals, which results in a valid interval schedule for an \stn, allowing efficient schedule execution under dynamic circumstances. Additionally, we note that an interval schedule can also serve as a mechanism to decouple a schedule, giving a partial answer to the last research question. In the fourth chapter, we investigate how to make use of the available flexibility to ensure that schedules are robust. We show that having a maximal total amount of flexibility does not imply that the schedule is as robust as possible: maximization might lead to a very skewed distribution of flexibility over the schedule. Different ways of distributing flexibility over a schedule are proposed and analyzed in an experimental setting. From the experiments it can be clearly concluded that sacrificing some of the total flexibility to improve the distribution of flexibility can have a positive influence on the robustness of the schedule. We also propose a different maximization strategy: one which maximizes the minimum of the interval sizes for the schedule. This strategy is shown to work especially well for small delays. So far we only discussed strategies concerning temporal flexibility, i.e., those in which start times remain flexible instead of fixed. Chapter 5 introduces a novel representation of solutions for planning problems in which not all ordering decisions needed to avoid resource contention are made in advance. This is achieved by grouping tasks which need to be executed sequentially together, in such a way that either ordering of the tasks remains feasible during execution time. An analysis using simulation experiments shows that this technique results in higher robustness, at the cost of somewhat lower resource utilization. The proposed algorithm to construct such schedules offers limited control over the size of the grouped tasks. The experiments show a slightly counter-intuitive results: schedules with larger groups offer lower robustness than those with smaller groups. A plausible explanation is the fact that delays can occur at any place in a schedule. Having multiple smaller groups instead of a few very large ones increases the chance that such a delay can be compensated for using a task group.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Coordinated Multi-Agent Planning and Scheduling
No full textComputer ScienceElectrical Engineering, Mathematics and Computer Scienc
Heuristics in dynamic scheduling: A practical framework with a case study in elevator dispatching
No full textDynamic scheduling problems are ubiquitous: traffic lights, elevators, planning of manufacturing plants, air traffic control, etc. Tasks have to be put on a timeline as smart as possible to reach certain goals. These goals may be related to production costs, the use of (scarce) resources, deadlines. These problems have often been regarded statically: a schedule is made that seems best for the situation as it is observed now. However, with dynamic problems, the situation changes continually. For example, you may assign passengers to elevators in a manner that seems optimal now, but a new passenger presses a button 3 seconds later, making you think: if I had known this before, I would have made a different schedule. This dissertation is about techniques to make schedules robust and/or flexible. A robust planning stands the tide of change: it only has to be modified slightly when change occurs. A flexible schedule makes it easy for future tasks to be inserted. Robustness and flexibility are two sides of the same medal. One is focused on currently known tasks, the other on future (yet unknown) tasks. The dissertation contains an elaborate case study on elevator dispatching. Various scheduling techniques have been tried, in simulation, on an existing building in Paris, of which detailed passenger data were available. Some of these techniques came out as promising. A remarkably successful technique involved advancing the scheduling horizon. Instead of focusing on individual passengers, this technique focused on elevators as a whole, making them finish whatever they're doing as soon as possible. On short term, this seemed worse for passengers (e.g., more stop overs), but on the long term, the average waiting and travelling times were significantly reduced.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Context-Aware Route Planning
No full textIn context-aware route planning, there is a set of transportation agents each with a start and destination location on a shared infrastructure. Each agent wants to find a shortest-time route plan without colliding with any of the other agents, or ending up in a deadlock situation. We present a single-agent route planning algorithm that is both optimal and conflict-free. We also present a set of experiments that compare our algorithm to finding a conflict-free schedule along a fixed path. In particular, we will compare our algorithm to the approach where the shortest conflict-free schedule is chosen along one of k shortest paths. Although neither approach can guarantee optimality with regard to the total set of agent route plans — and indeed examples can be constructed to show that either approach can outperform the other — our experiments show that our approach consistently outperforms fixed-path scheduling.Network Architectures & Services (NAS)Electrical Engineering, Mathematics and Computer Scienc
Coordinating autonomous planning and scheduling
No full textSoftware TechnologyElectrical Engineering, Mathematics and Computer Scienc
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
The world according to MARP
No full textIn multi-agent route planning (MARP), there is a set of agents each with a start location and a destination location on a shared infrastructure, and the goal of each agent is to reach its destination in the shortest possible time, without coming into conflict (e.g. because of a collision) with any of the other agents. The MARP problem is relevant in automated guided vehicle systems, with application domains in flexible manufacturing systems or at container terminals like Rotterdam or Singapore. Another application domain for MARP is airport taxi routing, where aircraft must taxi between runway and gate, while avoiding close proximity with other aircraft. In the literature, a number of approaches to MARP exist. The first is to have one planner make a plan for all agents. Because of its complete overview, the centralized planner can in principle find an optimal set of agent route plans. Unfortunately, finding an optimal set of plans is intractable (as we show in this thesis), and in practice optimal plans can only be found if there are not more than a handful of agents. A second approach, and the one we take in this thesis, is to let the agents plan one by one, each agent planning around the plans of the previous agents (in the sense that no conflict is introduced with any existing plans). In this prioritized approach (the agents plan in the order of their priority), it is possible to find an individually optimal route plan in reasonable time, although there is no guarantee that the combination of agent plans is also optimal. A third approach to MARP is to do very little planning (for example by choosing a fixed path between start and destination), and instead to check at every next step in the plan-execution phase whether it is safe to move forward, or whether a conflict will ensue. In this approach there are no guarantees for either local or global optimality, but it can be a convenient approach in dynamic environments, where unexpected changes can invalidate carefully crafted plans. If however there are no plans, then nothing can be disrupted, and any situation can be treated the same way. By contrast, the first two (planning) approaches to MARP require additional plan repair techniques to deal with unexpected incidents. We present a model for MARP in which the infrastructure is modeled as a graph of resources (like roads and intersections); each resource has a capacity, which is the maximum number of agents that may occupy the resource at the same time. A route plan is a sequence of resources each with an occupation time interval, and the objective in MARP is to find a set of agent route plans such that the capacities of the resources are never exceeded. In our model, we also identify a number of additional constraints that have to be satisfied depending on the application domain. For example, we formulate constraints to forbid overtaking, constraints that forbid cyclic plans, and constraints that require a minimum separation between agents of at least one empty resource. Even if no additional constraints need to be satisfied, finding an optimal solution to the MARP problem is intractable. Our route planning algorithms make use of free time windows on resources. A free time window is an interval during which an agent can make use of a resource without causing a conflict with any of the existing route plans. We search for a route plan by constructing a graph of the free time windows, and performing an adapted shortest-path search through this graph, which results in an optimal (shortest-time), conflict-free route plan for a single agent. Our contribution lies in the speed of our algorithm, which is much faster than previous optimal single-agent route planning algorithms. In addition, we also present a route planning algorithm that can find a conflict-free route plan along a sequence of locations (rather than from a start location to a single destination location), which is the first algorithm in its kind, as far as we know. Planning approaches to MARP require additional mechanisms to deal with unexpected incidents during plan execution. In this thesis, we consider vehicle incidents that temporarily immobilize an agent (which can be caused by e.g. a human that steps into the path of an agent). If, after the slowdown, all agents including the delayed agent ignore the disruption, then a deadlock situation can arise. In the literature there exists a mechanism that can prevent deadlocks, and thus ensure that each agent can reach its destination safely, albeit with a possible delay. This mechanism is based on the resource priority that agents inherit after the planning process: from the set of agent plans, we can infer the order in which agents visit a resource (and the first agent to visit a resource has the highest resource priority). The deadlock prevention mechanism is simply to respect these resource priorities during plan execution, which means that agents sometimes have to wait for a delayed agent with a higher priority. In some cases, there is no need to wait for a delayed agent, and the resource priority can be changed during plan execution without creating a deadlock situation. In the literature, one such priority-changing algorithm exists, but the conditions under which it allows a priority change are very strict, which limits the applicability of the algorithm. We developed a new priority-changing algorithm that allows changes in more situations, which therefore has the potential to achieve a bigger reduction in agent delay. Our algorithm makes use of a graph structure that can predict exactly which priority changes are safe, and which will lead to a deadlock. In our experiments we evaluated the robustness of agent route plans, i.e., the property of plans to remain efficient, in terms of minimizing delay, even if unexpected incidents necessitate minor plan revisions. Above, we described three schedule repair algorithms: either fully respect the resource priorities during plan execution, or allow some priority changes using the existing priority-changing algorithm, or using our new algorithm. Respecting resource priorities can be seen as a baseline approach to incident handling: if it results in short delays, then no priority changes are necessary; if it would result in long delays, then we can seek to reduce this delay by changing some priorities at run-time. In taxi route planning experiments on a model of Schiphol airport, the baseline method produced satisfactory results: in case there are only a few short incidents, then there is hardly any delay; in case there are many incidents of a long duration, then the average delay was still rarely more than 20% of the length of the agent plans. Experiments on other types of infrastructures (such as grid-like networks and small-world networks) also showed that delay is low for a small number of short incidents, but for a large number of long incidents, delays of around 100% were frequently reached. One reason why the results are so favourable for the airport experiments is that the locations of the start and destination points of the agents were not fully randomized, as aircraft agents travel between runways and gates. Hence, if aircraft agents use the same resource, then they are most likely heading in the same direction. Our experiments suggest that the most delay from incidents arises when agents that have to wait for each other travel in opposite directions. We also managed to reduce delay by changing priorities, and our algorithm, which produces the greatest number of priority changes, also managed the greatest reduction in delay. A different set of experiments evaluated the cost of the multi-agent plan (which can be measured by e.g. recording the finish time of the latest agent) that results from sequential single-agent planning, for arbitrary agent priorities. Under the assumption that the optimal set of agent priorities will result in a close-to-optimal global plan, then measuring the difference between the best and the worst observed set of priorities gives an indication of the worst-case global plan cost that can be obtained using prioritized planning. In our experiments, we tried 100 different sets of agent priorities for a single problem instance, and for each type of infrastructure, we tried numerous instances. The best results were again obtained for the airport infrastructure, and again the locations of the start and destination points seem to be the main reason: because all agents travel in more or less the same direction, they manage to organize themselves into flows, regardless of which agent is allowed to plan first. For other types of infrastructures, it proved to be important to have multiple routes between any two locations. Otherwise, if e.g. one road connects two parts of the infrastructure, then this road can become a bottleneck if agents on either side of the road need to cross; arbitrarily assigned priorities can then lead to a situation where the travel direction of the resource alternates with every other agent, which is much less efficient than many agents using the resource at the same time in the same direction. To conclude, we presented a prioritized approach to the multi-agent route planning problem. MARP has many important application domains like airport taxi routing and route planning for automated guided vehicles, and our new algorithm is fast enough to be applied to problem instances of realistic size. To deal with unexpected incidents, we have focussed on schedule repair methods, but in future work we can investigate how plan repair techniques (i.e., also allowing agents to choose a different route) can further reduce delay. Another direction of future research is how we can reduce the cost of the global plan. Our route planning algorithms are optimal for a single agent, and the combination of individually optimal route plans sometimes leads to high-quality global plans --- for example in the taxi route planning experiments, where the location of the start and destination points of the agents ensured that they travel in the same directions and therefore interfere little with each other. On other infrastructures, an arbitrary priority assignment can sometimes lead to a poor global plan. To improve global plan cost, one possibility is to find a better set of agent priorities. Another option is to investigate whether agents can coordinate before or during planning, such that an agent also takes into account the benefit of other agents during planning.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Auto-completion Algorithms for Geocoding Systems
No full textPresents new algorithms for meeting the specific requirements of auto-completion in the context of geocoding systems.Computer ScienceElectrical Engineering, Mathematics and Computer Scienc
Stochastic Scheduling of Train Maintenance Projects
No full textWe study the application of stochastic scheduling methods for dealing with the negative impact of uncertainty on the timely delivery of NedTrain maintenance projects. A stochastic scheduling problem includes a quantification of uncertainty by representing the duration of a maintenance activity with a probability distribution. The solution is no longer a schedule but a scheduling policy: a dynamic process for determining when to execute activities on-the-fly. Our objective is to find a policy that minimizes stochastic tardiness by expectation and also by variance, to minimize risk. We concentrate on the class of Early-Start (ES) policies. An ES policy is a PERT network representation of the projects in which the width of the partial order defined by the precedence edges is restricted such that resource requirement will not exceed resource availability. ES policies enable the use of standard PERT management practices (developed for handling uncertainty in projects with unlimited resources) to projects with limited resources (e.g., NedTrain projects). Simulation is considered as the only practical means to evaluate the objective function in stochastic scheduling. This approach is computationally expensive, especially for large (e.g., NedTrain-specific) instances with activity durations that exhibit high variability. We observe that circuit timing graphs in modern VLSI design use a PERT network-like representational mechanism. Statistical Static Timing Analysis (SSTA) is a new research area with a wealth of methods for solving the PERT problem on massive networks, offering high accuracy at low computational cost. We propose the use of SSTA techniques, treating a given ES policy as a circuit timing graph. This enables us to evaluate the objective function and more importantly to implement informed heuristics with efficiency. As a proof-of-concept we studied the use of Linear-Gaussian SSTA, applicable when activity durations exhibit Gaussian variability and may have linear interdependencies. Our other contribution is to propose efficient enumeration schemes for ES policies, overcoming the infeasibility of the existing scheme on problems of practical size. Experiments suggest that the proposed enumeration schemes in combination with SSTA establish a frame work for the design of competitive heuristic solvers, suitable for large-scale problem instances with high durational variability.Computer Science MScSoftware TechnologyElectrical Engineering, Mathematics and Computer Scienc
- …
