Schedule | EPFL Graph Search

A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are intended to take place. The process of creating a schedule — deciding how to order these tasks and how to commit resources between the variety of possible tasks — is called scheduling, and a person responsible for making a particular schedule may be called a scheduler. Making and following schedules is an ancient human activity. Some scenarios associate this kind of planning with learning life skills. Schedules are necessary, or at least useful, in situations where individuals need to know what time they must be at a specific location to receive a specific service, and where people need to accomplish a set of goals within a set time period. Schedules can usefully span both short periods, such as a daily or weekly schedule, and long-term plannin

A Reinforcement Learning Approach to Train Routing and Scheduling

Zora Oswald

Good train scheduling for a big network with many trains is very hard to achieve. As the trains are competing for the tracks with one another, the number of constraints grows rapidly. Trying to take advantage of emerging technologies in the areas of optimization and machine learning, the Swiss Federal Railways have created a challenge to find the best algorithm to solve this problem. Two algorithms to solve this task were implemented in this project. First, a greedy strategy trying to schedule all trains at their earliest possible and then solving conflict after conflict was reproduced. It is shown that this algorithm is able to keep up with the best methods existing. With the objective of generalizing and improving the result, a policy gradient method is then added to take on the most critical decisions that have to be made in every iteration of the first algorithm. Even though this second enhanced algorithm does not obtain optimal solutions, it is able to outperform the first one in a generalized task. Hence, it can be shown that reinforcement learning is applicable to the train routing and scheduling task and, more generally, in environments with an open structure.

2020

Energy-Efficient Co-Design Optimization of Many-Core Platforms for Big-Data Streaming Applications

Karim Kanoun

Big-Data streaming applications are used in several domains such as social media analysis, financial analysis, video annotation, surveillance, medical services and traffic prediction. These applications, running on different types of platforms from mobile devices to servers, are characterized by a highly-variable stochastic input data stream, stringent delay constraints and complex task graphs. Several software and hardware optimization techniques have been proposed to maximize the execution quality and the throughput of these applications and to minimize their energy consumption on many-core platforms. By analyzing the existing techniques, one can observe that most solutions classify as a hardware-based task-specific optimization, or as an operating system scheduler optimization, or yet as a load shedding mechanism at the application level. Each of these categories is limited in scope and can be blind to the nature of the program, the data being processed or the characteristics of the hardware. Big-Data streaming applications, due to their wide range of host hardware and content and dynamically-changing input streams, expose the fragmentation of the optimization techniques and create a clear need for a better approach. In this thesis, I propose a suite of energy-efficient hardware-software co-design techniques to bridge the gap between modern Big-Data streaming applications and existing many-core platforms. I choose to model the task graph of the class of applications I consider here by a direct acyclic graph (DAG). First, at the application layer, I propose a unified DAG monitoring solution to process online the general DAG model of the application and provide a set of relevant information that is leveraged at run time by a connected scheduler. At the operating system layer, I propose three different online scheduling solutions for many-core platforms which leverage the feedback from both the application and the hardware layers. The first scheduler addresses the problem of minimizing the energy consumption and the deadlines miss rates of multimedia applications. It takes advantage of the output of the DAG monitoring solution to adapt the mapping of the tasks of multimedia applications to the hardware according to the detected performance and targeted quality of service. The second and third schedulers address the problem of maximizing the quality and throughput and minimizing the energy consumption of Big-Data stream mining applications with single and multiple streams originating from different sources. To cope with the dynamically-changing Big-Data characteristics, the schedulers integrate machine-learning techniques to learn the environment dynamics and the application requirements and adapt the scheduling policy to the desired quality of service. I show that the proposed schedulers are able to scale the execution of data-mining applications to the system capability even in the presence of concept drift. Last, at the hardware layer, to address existing system architectures limitations and to increase even more the throughput, I propose a novel low-power many-core architecture for modern Big-Data stream mining applications that integrates a novel flexible memory hierarchy able to adapt to the dynamic data-driven nature of the input data stream.

EPFL2015

Disassembly scheduling

Hwa-Joong Kim

This dissertation focuses on disassembly scheduling, which is the problem of determining the quantity and timing of disassembling used or end-of-life products while satisfying the demand of their parts/components over a given planning horizon. The objective is to minimize the sum of purchase, setup, disassembly operation, and inventory holding costs. In general, disassembly scheduling is one of the important mid-term (or short-term) planning problems in disassembly systems. In contrast to assembly, disassembly systems have the special characteristic that a product diverges into multiple demand sources of parts/components. This makes the disassembly scheduling problem more complex than the ordinary production planning problems in assembly systems. We consider two versions of disassembly scheduling: the uncapacitated and capacitated version. For the uncapacitated version of the problem, three cases are considered: the two-level disassembly; the multi-level disassembly; and the multiple product types with parts commonality structures. The two-level disassembly structure describes the direct relationship between the product and its parts/components without intermediate subassemblies. Parts commonality implies that products or subassemblies share their parts and/or components. For the capacitated version of the problem, the case with single product type without parts commonality is considered. In the first part of this dissertation, we consider the case with the two-level disassembly structure. We propose a dynamic programming model after characterizing the properties of optimal solutions. Based on the dynamic programming model, an exact algorithm is proposed by which the optimal solutions can be obtained in polynomial time. The second part considers the case with the multi-level disassembly structure. An integer programming model is proposed to represent and optimally solve the case of single product type without parts commonality. Then, the model is extended to consider single and multiple product types with parts commonality. The results of computational experiments show that the proposed integer programming approach works well. The case with multiple product types and parts commonality is considered in the third part. A two-phase heuristic is proposed in which an initial solution is obtained using a linear programming relaxation, and then improved by perturbing the initial solution using a dynamic programming algorithm with look-ahead check, together with methods of generating new solutions and checking their feasibilities. The results of computational experiments show that the proposed heuristic can give good solutions within short computation time. We consider in the last part the resource capacity restrictions over the planning horizon, which makes the problem more realistic. To solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The results of computational experiments show that the proposed heuristic can give near optimal solutions within a short amount of computation time.

EPFL2005