Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied. / text

Hydropower is the world’s largest source of renewable electricity generation. Hydropower plants with reservoirs provide flexibility to the power systems. Efficient planning techniques improve the flexibility of the power systems and reduce carbon emissions, which is needed in power systems experiencing a rapid change in balance between power production and consumption. This is due to increasing amount of renewable energy sources, such as wind and solar power. Hydropower plants have low operating costs and are used as base power. This thesis focuses on weekly planning of hydropower in systems with large volumes and varying power generation and a literature review and a maintenance scheduling method are presented. The topic of hydropower planning is well investigated and various research questions have been studied under many years in different countries. Some of the works are summarized and discussed in literature reviews, which are presented in this thesis. First, some reviews are presented, which covers several aspects of hydropower planning. Literature reviews for long term, mid term and short term planning, respectively, are described. Maintenance scheduling in power systems consists of preventive and corrective maintenance. Preventive maintenance is performed at predetermined intervals according to a prescribed criteria. This type of maintenance is important for power producers to avoid loss in electricity production and loss in income. The maintenance scheduling for hydropower plants prevent these phenomena since spill in the reservoirs and wear on the turbines can be avoided. Usually, the maintenance in hydropower plants is performed on the turbines or at the reservoir intake. A deterministic and a stochastic method to solve a mid term maintenance scheduling problem formulated as a Mixed Integer Linear Programming using dynamic programming is presented. The deterministic method works well in terms of computational time and accuracy. The stochastic method compared to the deterministic method yields a slightly better result at the cost of a need for larger computational resources. / Vattenkraft är världens största källa till förnyelsebar elproduktion. Vattenkraftverk med magasin erbjuder flexibilitet till elkraftsystem. Effektiva planeringsmetoder förbättrar flexibiliteten hos kraftsystemen och minskar koldioxidutsläppen, vilket är nödvändigt i kraftsystem som utsätts för snabb förändring med obalans mellan produktion och konsumtion av effekt. Detta beror på ökad andel förnyelsebara energikällor, som vind- och solkraft, i kraftsystemen. Vattenkraftverk har låga driftkostnader och används som baskraft. Den här avhandlingen fokuserar på veckoplanering av vattenkraft i kraftsystem med stora volymer och varierande kraftproduktion, samt en litteraturstudie och en metod för underhållsplanering presenteras.    Ämnet vattenkraftplanering är väl undersökt och varierande forskningsfrågor har studerats under många år i olika länder. En del av arbetena sammanfattas och diskuteras i litteraturstudier, vilka presenteras i den här avhandlingen. Först presenteras några litteraturstudier, som täcker flera aspekter av vattenkraftplanering. Litteraturstudier, för långtids-, medeltidsplanering, respektive korttidsplanering beskrivs.    Underhållsplanering i elkraftsystem består av förebyggande och korrigerande underhåll. Förebyggande underhåll utförs vid förutbestämda intervall enligt förbestämda kriterier. Denna typ av underhåll är viktig för att kraftproducenter ska kunna undvika förlorad elproduktion och förlorad inkomst. Underhållsplaneringen för vattenkraftverk förebygger dessa fenomen, eftersom spill i magasinen och slitage på turbinerna kan undvikas. Vanligen utförs underhållen i vattenkraftverken på turbinerna eller vid intaget i magasinet. En deterministisk metod och en stokastisk metod att lösa ett medeltidsplaneringsproblem, formulerat som ett blandat heltalsprogrammeringsproblem presenteras. Den deterministiska metoden fungerar väl i termer av beräkningstid och noggrannhet. Den stokastiska metoden jämfört med den deterministiska metoden ger ett något bättre resultat dock till priset av ett behov av större datorresurser. / <p>QC 20220920</p>