Daily drayage operations involve moving loaded or empty equipment between customer locations and rail ramps. Drayage orders are generally pickup and delivery requests with time windows. The repositioning of empty equipment may also be required in order to facilitate loaded movements. The drayage orders are satisfied by a heterogeneous fleet of drivers. Driver routes must satisfy various operational constraints. In the first part of the dissertation, our goal is to minimize the cost of daily drayage operations in a region on a given day. We present an optimization methodology for finding cost-effective schedules for regional daily drayage operations. The core of the formulation is a set partitioning model whose columns represent routes. Routes are added to the formulation by column generation. We present numerical results for real-world data which demonstrate that our methodology produces low cost solutions in a reasonably short time. The second part of the dissertation addresses minimizing total empty mileage when driver capacity is not restrictive and new orders are added to the problem in an online fashion. We present a lower bound for the worst case guarantee of any deterministic online algorithm. We develop a solution methodology and provide results for the performance of different scheduling policies and parameters in a simulated environment. In the third part of the dissertation, we study a system with one rail ramp and one customer location which is served by a single driver. The problem has discrete time periods and at most one new order is released randomly each time period. The objective is to maximize the expected number of orders covered. With this simple problem, we seek to learn more about route planning for a single driver under uncertainty. We prove that carrying out an order ready to be picked up at the driver's current location is optimal for the case with one customer location. We show that the structure of the optimal policies is not simple and depends on various parameters. We devise a simple policy which yields provably near-optimal results and identify a case for which that policy is optimal.

Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d’ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l’avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l’ordonnancement en ligne. Dans un problème d’ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L’analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d’une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l’aide de l’analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure. / This thesis proposes and evaluates some online algorithms for machine scheduling problems. Deterministic scheduling models have been extensively studied in the literature. One of the basic assumptions of these models is that all the information is known in advance. However, this assumption is usually not realistic. This observation promotes the emergence of online scheduling. In online scheduling problems, an online algorithm has to make decisions without future information. Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared with the performance of an a posteriori optimal solution where the sequence of requests is known. In the framework of competitive analysis, the performance of an online algorithm is measured by its competitive ratio. We mainly deal with two online paradigms: the one where jobs arrive over list and the one where jobs arrive over time. Based on these two paradigms, we consider different models: single machine, two identical parallel machines, two uniform parallel machines, batch processing machine and open shop. For each of the problems, we prove a lower bound of competitive ratios and propose online algorithms. Then we further measure the worst case performance of these algorithms. For some problems, we can show that the algorithms we proposed are optimal in the sense that their competitive ratios match the lower bounds.

Mgr. Tomáš Ebenlendr Combinatorial algorithms for online problems: Semi-online scheduling on related machines Abstract of doctoral thesis We construct a framework that gives optimal algorithms for a whole class of scheduling problems. This class covers the most studied semi-online variants of preemptive online scheduling on uniformly related machines with the objective to minimize makespan. The algorithms from our framework are deterministic, yet they are optimal even among all randomized algorithms. In addition, they are optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. We provide new lower bound of 2.112 for the original online problem. The (deterministic) upper bound is e ≈ 2.718 as there was known e-competitive randomized algorithm before. Our framework applies to all semi-online variants which are based on some knowledge about the input sequence. I.e., they are restrictions of the set of valid inputs. We use our framework to study restrictions that were studied before, and we derive some new bounds. Namely we study known sum of processing times, known maximal processing time, sorted (decreasing) jobs, tightly grouped processing times, approximately known optimal makespan and few combinations. Based on the analysis...

We study online scheduling policies for buffer management models, in which packets are arriving over time to a buffer of a network switch to be sent through its single output port. However, the bandwidth of the port is limited and some packets need to be dropped, based on their weights. The goal of the scheduler is to maximize the weighted throughput, that is, the total weight of packets transmitted. Due to the natural lack of information about future, an optimal performance cannot be achieved, we thus pursue competitive analysis and its refinements to analyze online algorithms on worst-case inputs. Specifically, in the first part of the thesis, we focus on a simple online scheduling model with unit-size packets and deadlines, called Bounded-Delay Packet Scheduling. We design an optimal φ-competitive deterministic algo- rithm for the problem, where φ ≈ 1.618 is the golden ratio. It is based on a detailed understanding of an optimal schedule of pending packets, called the plan, which may be of independent interest. We also propose a semi-online setting with lookahead that allows the algorithm to see a little bit of future, namely, packets arriving in the next few steps. We provide an algorithm with lookahead for instances in which each packet can be scheduled in at most two consecutive slots and prove lower...

There is no doubt Medical Devices have a crucial role in hospital processes such as surgeries and therapeutic procedures. Medical devices available in hospitals are of two types; reusable and non-resalable medical devices. Reusable medical devices are washed and sterilized after each use. The process of sterilizing medical devices is performed in the sterilization department. Each medical device travels through a cycle each time it is utilized. It is explicit that any part of the sterilization cycle that delays the process can cause serious problems for hospitals’ performance. The washing step of the sterilization process has been a bottleneck in the system. Thus, optimization approaches can be highly advantageous to improve this bottleneck. The data of the medical devices are usually unknown prior to the scheduling process since the finishing time of the surgeries are not known in advance. Thus, there is no information available on the ready time of medical devices to be sterilized. Due to this factor, to develop applicable solutions, it is critical to consider this problem as an online problem and develop online scheduling methods. In this thesis, we take advantage of mathematical programming and heuristic algorithms to solve both the offline and online settings of the problem. We model the washing step of the sterilization cycle as a scheduling problem. Batch scheduling and bin packing, two well-known optimization approaches, are used for this purpose. Medical devices are batched together first and then scheduled on machines to reduce the total washing time of all medical devices. First, a mathematical model for the offline problem is provided and tested to solve the problem. Then a series of heuristic algorithms are developed using the batch scheduling approach for solving both offline and online problems. Moreover, a special case with divisible job sizes and equal release dates is studied. It was proved that for the strongly divisible sequence the First Fit Increasing algorithm finds the optimal solution, also for the weakly divisible sequence a Dynamic Programming algorithm is developed. Finally, we couple optimization with simulation to test the impact of the optimization of the washing step on the entire sterilization system. Moreover, since the next step of the sterilization cycle, the sterilization step, is very similar to the washing step, we also implement the developed heuristics in this step to evaluate its performance and improve it further. The results show that as long as the washing step is optimized it does not differ which algorithm is used in the sterilization step, thus, the optimization of this step is not necessary.

The consumer market of today is characterized by emphasis on superior customer satisfaction and personalization of services. This entails higher customer expectations on organizations, which also includes the workforce scheduling processes in which the consumers expect more decision-power to dictate what they want, when and where they want services to be delivered. For organizations that deliver on-site services, the routing aspect becomes an important part of the scheduling process. Literature on Workforce Scheduling and Routing Problems (WSRP) seldom relate to characteristics of the more dynamic consumer market. As the markets and consumer needs become more flexible, the relevance for research concerning these characteristics increases. This study addresses this by reviewing current literature and present common solution methodologies applied to WSRP, as well as the effects of the online scheduling characteristics. With this as a foundation, a discussion is provided of how WSRP and online scheduling can be combined in order to improve resource utilization and minimize travel time for an on-site service provider. The overall aim of the study is to investigate how an online WSRP with exact time windows can be formulated and solved. The result is a four-stage hybrid method including linear integer programming and constructive heuristics with the objective to minimize travel time, idle time, and the makespan in the schedules. A case study has been conducted on an on-site service provider, and by applying the proposed hybrid methodology on the case company’s scheduling process, results have been obtained that demonstrates improvements of travel time and resource utilization. The study also demonstrate that the appliance of flexible travel times and product dependent service times have positive impact on the quality of the generated schedules. A key insight is that organizations working with exact time windows have to be aware of the trade-off between customer preferences and operational efficiency in day-to-day operations. Thus, organizations have to decide what holds most importance to the organization’s long-term success.

Avec les préoccupations environnementales croissantes liées aux émissions de carbone et la chute rapide des prix des batteries, la part de marché des véhicules électriques (EV) augmente rapidement. Le nombre croissant de EV ainsi que les progrès sans précédent dans la capacité de la batterie et de la technologie entraîne une augmentation drastique de la demande totale d'énergie destinée aux véhicules électriques. Cette forte demande de charge rend complexe le problème de planification de la charge. Même en prenant avantage de la propriété reportable des demandes de charge et d'une planification adéquate, la demande globale pourrait dépasser le taux de charge tolérable des stations, étant donné les contraintes physiques des dispositifs de charge et des transformateurs. Le principal défi est la nécessité de concevoir des solutions en ligne puisque, dans la pratique, l'ordonnanceur ne dispose d'aucune information sur les arrivées futures d'EV. Cette thèse étudie le problème d'ordonnancement des EV en ligne et fournit trois contributions principales. Premièrement, nous démontrons que le problème classique de la programmation en ligne des tâches sensibles aux échéances avec des valeurs partielles est similaire au problème d'ordonnancement EV et étudions l'extension de la programmation des charges EV en prenant en compte de la limite de traitement des travaux. Le problème réside dans la catégorie des problèmes d'ordonnancement en ligne couplés dans le temps sans disponibilité d'informations futures. Le premier algorithme proposé est déterministe, tandis que le second est randomisé et bénéficie d'une complexité de calcul plus faible. Deuxièmement, nous formulons un problème de maximisation du bien-être social pour la planification de la charge des EV avec une contrainte de capacité de charge. Nous avons conçu des algorithmes d'ordonnancement de charge qui non seulement fonctionnent dans un scénario en ligne, mais aussi qui répondent aux deux principaux défis suivants : (i) fournir un engagement à l'arrivée ; (ii) garantir la résistance aux stratégies (de groupe). Des simulations approfondies utilisant des traces réelles démontrent l'efficacité de nos algorithmes d'ordonnancement en ligne par rapport à la solution hors-ligne optimale non-engagée. La troisième contribution concerne la planification en ligne des véhicules électriques dans un réseau de recharge adaptatif (ACN) avec des contraintes de pics locaux et globaux. Nous avons conçu un algorithme d'ordonnancement primal-dual de faible complexité qui atteint un rapport d'approximation borné. Des résultats expérimentaux détaillés basés sur des traces montrent que les performances des algorithmes en ligne proposés sont proches de l'optimum hors ligne et surpassent les solutions existantes / With the increased environmental concerns related to carbon emission, and rapid drop in battery prices (e.g., 35% drop in 2017), the market share of Electric Vehicles (EVs) is rapidly growing. The growing number of EVs along with the unprecedented advances in battery capacity and technology results in drastic increase in the total energy demand of EVs. This large charging demand makes the EV charging scheduling problem challenging. The critical challenge is the need for online solution design since in practical scenario the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. This thesis studies online EV scheduling problem and provides three main contributions. First, we demonstrate that the classical problem of online scheduling of deadlinesensitive jobs with partial values is similar to the EV scheduling problem and study the extension to EV charging scheduling by taking into account the processing rate limit of jobs as an additional constraint to the original problem. The problem lies in the category of time-coupled online scheduling problems without availability of future information. Using competitive ratio, as a well-established performance metric, two online algorithms, both of which are shown to be (2 − 1/U)-competitive are proposed, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. Second, we formulate a social welfare maximization problem for EV charging scheduling with charging capacity constraint. We devise charging scheduling algorithms that not only work in online scenario, but also they address the following two key challenges: (i) to provide on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly required; (ii) to guarantee (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Third, we tackle online scheduling of EVs in an adaptive charging network (ACN) with local and global peak constraints. Two alternatives in resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). For the fractional model, both offline and online algorithms are devised. We prove that the offline algorithm is optimal. We prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases

Submitted by Gilmara Espino (gilmara.espino@gpes.com.br) on 2018-06-13T23:25:16Z No. of bitstreams: 1 ESPINO_Economia compartilhada(2).pdf: 3950663 bytes, checksum: 40cfe7ac547a831cd83185c617d92725 (MD5) / Approved for entry into archive by Simone de Andrade Lopes Pires (simone.lopes@fgv.br) on 2018-06-14T00:56:25Z (GMT) No. of bitstreams: 1 ESPINO_Economia compartilhada(2).pdf: 3950663 bytes, checksum: 40cfe7ac547a831cd83185c617d92725 (MD5) / Approved for entry into archive by Isabele Garcia (isabele.garcia@fgv.br) on 2018-06-14T17:09:42Z (GMT) No. of bitstreams: 1 ESPINO_Economia compartilhada(2).pdf: 3950663 bytes, checksum: 40cfe7ac547a831cd83185c617d92725 (MD5) / Made available in DSpace on 2018-06-14T17:09:42Z (GMT). No. of bitstreams: 1 ESPINO_Economia compartilhada(2).pdf: 3950663 bytes, checksum: 40cfe7ac547a831cd83185c617d92725 (MD5) Previous issue date: 2018-06-13 / Avaliar a atratividade de um mercado é fundamental em decisões sobre investimento em uma determinada empresa ou segmento de negócio. Setores específicos requerem conhecimentos particulares, nem sempre percebidos em estudos de viabilidade conduzidos com base em premissas generalistas. Recentemente, um súbito crescimento da oferta de novas empresas de economia compartilhada competindo como plataformas de agendamento de consultas médicas fez levantar a questão sobre a atratividade desse negócio para o mercado de saúde. Esse estudo apresenta os fatores sociais, econômicos e tecnológicos que explicam essa intensificação de competidores e, também, as barreiras que ainda dificultam a expansão dessas plataformas no Brasil. Mais do que compreender o fenômeno, os resultados apresentam um cenário atual sobre o ambiente de saúde e percepção dos usuários. É, portanto, conhecimento que pode ser aplicado a estudos de viabilidade de outros produtos ou serviços que desejam competir no segmento de saúde. A análise, embasada na literatura pesquisada e nos dados combinados de questionário dirigido, entrevista e cliente oculto, conclui pela tendência de arrefecimento do interesse em investimentos em empresas que atuem exclusivamente como plataformas de agendamento de consultas, e aponta para uma organização do mercado mais concentrada, com pequenos concorrentes diversificando seus produtos e serviços para se manterem competindo. / The assessment of a market attractiveness is critical when deciding to invest in a new company or business segment. Specific sectors require specific knowledge, not always perceived in feasibility studies conducted on generalist assumptions. Recently, a sudden expansion of sharing economy companies offering online scheduling medical platforms has raised the issue of this particular market. This study presents the social, economic and technological factors that explain the increase of competitors and also explore the existing market barriers that makes the diffusion of this kind of platform so difficult in Brazil. More than understanding the phenomenon, the outcome presents a current overview about the Brazilian health environment and the users’ perception. Therefore, it’s a knowledge that can be applied to feasibility studies of other products or services that wish to compete in the Health sector. The analysis based on evidence from researched literature, interviews, survey and observation (hidden customer) concludes in direction to the lessen of interest by investments in companies that act exclusively on online-scheduling medical platforms based on sharing economy; and point to a more concentrated market with fewer small competitors who need to diversify their products and services in order to keep themselves competitive.

Immersion based technologies such as Augmented Reality (AR), Virtual Reality (VR) and Mixed Reality (MR), together falling under the umbrella of Extended Reality (XR) have taken the world by storm in the recent past. However, with the growing market and the increasing number of applications of XR, multiple challenges have arisen. To maintain acceptable levels of motion-to-photon latency, there is a need to serve the users with ultra low latency and with high reliability. To provide high quality rendering, these solutions have traditionally been deployed with wired connections, but severely inhibiting user mobility. Thus, the need to develop wireless solutions promising ultra low latency and high reliability emerges. Cloud/Edge based solutions promise to provide great dividends in this regard but it still remains crucial to understand how different scheduling policies perform against one another in terms of average throughput, mean system time, the number of UEs which can be serviced simultaneously etc. In this thesis, we explore how online packet scheduling policies such as first-come-first-serve, earliestdeadline-first, maximum weight scheduling etc. compare against other Quality of Experience(QoE)/ packet weight aware online scheduling policies and also against optimal offline schemes such as maximum-weighted-bipartitematching. We perform a detailed analysis of how these policies fare by studying various metrics such as the average-packet system time, competitive ratios, packet drop percentages and weight throughput, amongst others. Finally, we also explore how the introduction of multi-layered video encoding impacts XR service. Amongst the findings of the thesis, we conclude that it is possible to come up with solutions such as EDFα (which is a deadline and weight aware derivative of the earliest deadline first scheduling policy), which can either increase the weight throughput when compared to other baselines while also providing lesser packet drops and lower average system times for the scheduled packets. This algorithm can be further tuned by varying α to accordingly alter the weight throughput, system time and packet drop ratio depending on the precise user application. Additionally, we establish with the help of simulations that the introduction of multi-layered video encoding conclusively helps in reducing the average system time and eventually allows for more users to be accommodated in an XR based system at the cost of worsening video quality. / Immersionsbaserade teknologier som Augmented Reality (AR), Virtual Reality (VR) och Mixed Reality (MR), som tillsammans faller under paraplyet Extended Reality (XR) har tagit världen med storm på senare tid. Men med den växande marknaden och det ökande antalet tillämpningar av XR har flera utmaningar uppstått. För att förhindra åksjuka hos användare och för att upprätthålla acceptabla nivåer av rörelse-till-foton-latens, finns det ett behov av att betjäna användarna med ultralåg latens och med hög tillförlitlighet. För att ge högkvalitativ rendering har dessa lösningar traditionellt implementerats med trådbundna anslutningar, men de hämmar kraftigt användarens rörlighet. Därför uppstår behovet av att utveckla trådlösa lösningar som lovar ultralåg latens och hög tillförlitlighet. Moln/Edge-baserade lösningar lovar att ge stor utdelning i detta avseende, men det är fortfarande viktigt att förstå hur olika schemaläggningspolicyer fungerar mot varandra när det gäller genomsnittlig genomströmning, genomsnittlig systemtid, antalet UE:er som kan betjänas samtidigt etc. I den här avhandlingen undersöker vi hur online-paketschemaläggningspolicyer som round robin, först till kvarnförst-kvarn, tidigast-deadline-först, schemaläggning för maximal vikt etc. jämförs med andra Quality of Experience (QoE)/Viktmedvetna onlineschemaläggningspolicyer och även mot optimala offline-scheman såsom maximalt viktad-bipartite-matchning. Vi utför en detaljerad analys av hur dessa policyer klarar sig genom att studera olika mätvärden, såsom den genomsnittliga paketets systemtid, konkurrensförhållanden, procentsatser för paketnedgång och viktad genomströmning, bland annat. Slutligen undersöker vi också hur introduktionen av flerskiktad videokodning påverkar XRtjänsten. Bland resultaten av avhandlingen drar vi slutsatsen att det är möjligt att komma med lösningar som EDFα (som är en deadline- och viktmedveten derivata av Earliest deadline first scheduling policy), som antingen kan öka den viktade genomströmning jämfört med andra baslinjer samtidigt som det ger mindre paketnedgångar och lägre genomsnittliga systemtider för de schemalagda paketen. Denna algoritm kan ställas in ytterligare genom att variera α för att följaktligen ändra den viktade genomströmningen, systemtiden och paketnedgångshastigheten beroende på den exakta användarapplikationen. Dessutom fastställer vi med hjälp av simuleringar att införandet av flerskiktsvideokodning definitivt hjälper till att minska den genomsnittliga systemtiden och så småningom tillåter fler användare att få plats i ett XR-baserat system.