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

Amusement parks are a huge business. Guest experiences determine the success or failure for an amusement park. This report suggests an approach to improve guest experience by managing guest flow. The guest happiness optimization problem is formulated into a visitor routing management model. The constraints for this model include attraction attributes and guest behavior. To build the attraction constraints, their information is first gathered from internet, field studies and surveys, and then input into simulation software. Constraints on guest behavior are set up with a literature study and a guest survey. A two phase heuristic is developed to solve this problem with constraints. Candidate routes are generated with a route construction algorithm in the first phase. Visitor distribution and selection on these candidate routes are determined in the second phase using a mixed integer programming solver. Visitor routes are then recommended to the park’s operator side, for them to distribute to guests visiting on their vacations. Data from Disney Epcot are collected and applied in the case study to implement the methodology in this report. Attraction operations capability is maintained at the current level with no additional cost for the project, while guest satisfaction is improved by ensuring the number and type of attractions they visit. In addition, average waiting time for visitors is reduced by at least 70% in the recommended operation strategy. / text

The focus of this dissertation is solution strategies for stochastic mixed-integer programs with special structures. Motivation for the methods comes from the relatively sparse number of algorithms for solving stochastic mixed-integer programs. Two stage models with finite support are assumed throughout. The first contribution introduces the nodal decision framework under private information restrictions. Each node in the framework has control of an optimization model which may include stochastic parameters, and the nodes must coordinate toward a single objective in which a single optimal or close-to-optimal solution is desired. However, because of competitive issues, confidentiality requirements, incompatible database issues, or other complicating factors, no global view of the system is possible. An iterative methodology called the nodal decomposition-coordination algorithm (NDC) is formally developed in which each entity in the cooperation forms its own nodal deterministic or stochastic program. Lagrangian relaxation and subgradient optimization techniques are used to facilitate negotiation between the nodal decisions in the system without any one entity gaining access to the private information from other nodes. A computational study on NDC using supply chain inventory coordination problem instances demonstrates that the new methodology can obtain good solution values without violating private information restrictions. The results also show that the stochastic solutions outperform the corresponding expected value solutions. The next contribution presents a new algorithm called scenario Fenchel decomposition (SFD) for solving two-stage stochastic mixed 0-1 integer programs with special structure based on scenario decomposition of the problem and Fenchel cutting planes. The algorithm combines progressive hedging to restore nonanticipativity of the first-stage solution, and generates Fenchel cutting planes for the LP relaxations of the subproblems to recover integer solutions. A computational study SFD using instances with multiple knapsack constraint structure is given. Multiple knapsack constrained problems are chosen due to the advantages they provide when generating Fenchel cutting planes. The computational results are promising, and show that SFD is able to find optimal solutions for some problem instances in a short amount of time, and that overall, SFD outperforms the brute force method of solving the DEP.

This dissertation discusses two independent topics. The first part of the dissertation relates three theories of international economics (comparative advantage, competitive advantage, and competitiveness), and formulates the thesis that incorporating them in the form of readily available individual competitiveness indicators in OR/MS models offers promise to enhance decision-support for the strategic planning of global supply chains in general, and for locating facilities in particular. The objectives of this research were to relate each of these theories and to describe their interrelationships; to describe measures provided by two well-known annual competitiveness reports; and to illustrate application of the theories as a means of supporting the thesis of the research, and justifying the research questions we pose for future research. While this research discusses topics relative to the broader background of global supply chain design, it illustrates applications associated with facility location, a component of the global supply chain design. In the last chapter of the first part of the dissertation, we provide a vision to foster future research that will enhance the profitability of international enterprises under NAFTA. The second part of the dissertation deals with the DSCR model with capacity expansion and contraction. The strategic dynamic supply chain reconfiguration (DSCR) problem is to prescribe the location and capacity of each facility, select links used for transportation, and plan material flows through the supply chain, including production, inventory, backorder, and outsourcing levels. The objective is to minimize total cost. The configuration must be dynamically redesigned over time to accommodate changing trends in demand and/or costs by opening facilities, expanding and/or contracting their capacities, and closing facilities. The problem involves a multi-period, multi-product, multi-echelon supply chain. Research objectives are alternative formulations of DSCR and tests that identify the computational characteristics of each model to determine if one offers superior solvability in comparison with the others. To achieve the first objective, we present an initial MIP model, a refined model that relates decision variables according to a convenient structure, and branch and price (B&P) schemes for the refined model. We found that the network-based formulation offered superior solvability compared to the traditional formulation.

In this thesis modelling and solution methods for portfolio optimisation are presented. The investigations reported in this thesis extend the Markowitz mean-variance model to the domain of quadratic mixed integer programming (QMIP) models which are 'NP-hard' discrete optimisation problems. In addition to the modelling extensions a number of challenging aspects of solution algorithms are considered. The relative performances of sparse simplex (SSX) as well as the interior point method (IPM) are studied in detail. In particular, the roles of 'warmstart' and dual simplex are highlighted as applied to the construction of the efficient frontier which requires processing a family of problems; that is, the portfolio planning model stated in a parametric form. The method of solving QMIP models using the branch and bound algorithm is first developed; this is followed up by heuristics which improve the performance of the (discrete) solution algorithm. Some properties of the efficient frontier with discrete constraints are considered and a method of computing the discrete efficient frontier (DEF) efficiently is proposed. The computational investigation considers the efficiency and effectiveness in respect of the scale up properties of the proposed algorithm. The extensions of the real world models and the proposed solution algorithms make contribution as new knowledge.

In April 2008, the Ontario government announced its top two healthcare priorities for the next 4 years, one of which is reducing wait time in emergency rooms. To study the wait time in emergency rooms or any other departments in a hospital, one must investigate resource planning, scheduling, and utilization within the hospital. This thesis provides hospitals with a set of simulation and optimization tools to help identify areas of improvement, particularly when there are a number of alternatives under consideration. A simulation tool (a Monte Carlo simulation model) estimates patient demand for beds in a hospital during a typical week. Two optimization tools (an integer programming mathematical model and a heuristics model) demonstrate opportunities for smoothing the patient demand for beds by adjusting the operating room schedule.

In April 2008, the Ontario government announced its top two healthcare priorities for the next 4 years, one of which is reducing wait time in emergency rooms. To study the wait time in emergency rooms or any other departments in a hospital, one must investigate resource planning, scheduling, and utilization within the hospital. This thesis provides hospitals with a set of simulation and optimization tools to help identify areas of improvement, particularly when there are a number of alternatives under consideration. A simulation tool (a Monte Carlo simulation model) estimates patient demand for beds in a hospital during a typical week. Two optimization tools (an integer programming mathematical model and a heuristics model) demonstrate opportunities for smoothing the patient demand for beds by adjusting the operating room schedule.

abstract: This research by studies the computational performance of four different mixed integer programming (MIP) formulations for single machine scheduling problems with varying complexity. These formulations are based on (1) start and completion time variables, (2) time index variables, (3) linear ordering variables and (4) assignment and positional date variables. The objective functions that are studied in this paper are total weighted completion time, maximum lateness, number of tardy jobs and total weighted tardiness. Based on the computational results, discussion and recommendations are made on which MIP formulation might work best for these problems. The performances of these formulations very much depend on the objective function, number of jobs and the sum of the processing times of all the jobs. Two sets of inequalities are presented that can be used to improve the performance of the formulation with assignment and positional date variables. Further, this research is extend to single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. These problems have been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first single machine interfering problem (P1), the criteria of minimizing total completion time and number of tardy jobs for the two sets of jobs is studied. A Forward SPT-EDD heuristic is presented that attempts to generate set of non-dominated solutions. The complexity of this specific problem is NP-hard. The computational efficiency of the heuristic is compared against the pseudo-polynomial algorithm proposed by Ng et al. [2006]. In the second single machine interfering job sets problem (P2), the criteria of minimizing total weighted completion time and maximum lateness is studied. This is an established NP-hard problem for which a Forward WSPT-EDD heuristic is presented that attempts to generate set of supported points and the solution quality is compared with MIP formulations. For both of these problems, all jobs are available at time zero and the jobs are not allowed to be preempted. / Dissertation/Thesis / Ph.D. Industrial Engineering 2012

Submitted by Marcelo Ferreira (clikmarcelo@yahoo.com.br) on 2018-09-05T04:31:34Z No. of bitstreams: 1 Tese de Marcelo Ferreira - Doutorado em Matemática.pdf: 2503649 bytes, checksum: 7e5babb359afbdff94f0d88f504985c5 (MD5) / Rejected by Elza Mitiko Sato null (elzasato@ibilce.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo: Problema 01) A paginação deve ser sequencial, iniciando a contagem na folha de rosto e mostrando o número a partir da introdução, a ficha catalográfica ficará após a folha de rosto e não deverá ser contada, você iniciou a contagem na página que contém a lista de figuras. A correção deve ser feita também no sumário. OBS:-Estou encaminhando via e-mail o template/modelo das páginas pré-textuais para que você possa fazer as correções, sugerimos que siga este modelo pois ele contempla as normas da ABNT Lembramos que o arquivo depositado no repositório deve ser igual ao impresso, o rigor com o padrão da Universidade se deve ao fato de que o seu trabalho passará a ser visível mundialmente. Agradecemos a compreensão. on 2018-09-05T13:47:24Z (GMT) / Submitted by Marcelo Ferreira (clikmarcelo@yahoo.com.br) on 2018-09-05T17:21:36Z No. of bitstreams: 1 Tese Marcelo Ferreira.pdf: 2501829 bytes, checksum: 90e5dbff7459a9f26f354110d615fe46 (MD5) / Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2018-09-05T18:50:17Z (GMT) No. of bitstreams: 1 ferreira_m_dr_sjrp.pdf: 2463292 bytes, checksum: c3ef62f0a5f3a7e55c2010f641a09d3c (MD5) / Made available in DSpace on 2018-09-05T18:50:17Z (GMT). No. of bitstreams: 1 ferreira_m_dr_sjrp.pdf: 2463292 bytes, checksum: c3ef62f0a5f3a7e55c2010f641a09d3c (MD5) Previous issue date: 2018-07-31 / Nessa tese abordamos dois problemas reais identificados no processo produtivo de indústrias de embalagens de papelão ondulado, que denotaremos por Problema de Minimização de Trocas de Gramaturas e Rolos Corrugadores (PMTGRC) e Problema da Alocação de Bobinas no Corrugador (PABC). Ambos os problemas ocorrem no corrugador, máquina multiestágio que produz as chapas de papelão ondulado. O PMTGRC surge da necessidade de minimizar trocas de gramaturas e rolos corrugadores durante o processo de produção dos boletins, uma vez que cada boletim traz as gramaturas específicas das camadas da chapa, além do tipo de onda empregada no(s) miolos(s). O sequenciamento dos boletins impacta na quantidade de mudanças de gramaturas nos porta-bobinas e se haverátrocaderoloscorrugadoresparadoisboletinssubsequentes. Astrocasdegramaturas impactam em custos de transporte de bobinas e as trocas de rolos corrugadores impactam em perda de produtividade. Para o PMTGRC propomos quatro modelos inéditos de programação inteira capazes de integrar essas duas considerações. O PABC integra várias considerações relacionadas à alocação das bobinas no corrugador, como por exemplo, a minimização das sobras não aproveitáveis e das quantidades de consumos parciais, fatores que influenciam diretamente nos custos de produção. Um modelo linear inteiro misto inédito é proposto, determinando quais bobinas serão utilizadas em cada porta-bobinas. Além disso, propomos uma estratégia de sequenciamento das bobinas em cada porta-bobina, evitando paragens no corrugador. Uma série de testes computacionais utilizando instâncias geradas com base em dados reais foram realizados. Os resultados indicam que os modelos foram eficientes em tratar os problemas propostos. / In this thesis we approached two real problems identified over the productive process of corrugated cardboard industries, which we will denote as the Minimization of Converting Weights and Corrugators Problem (MCWCP) and the Corrugators Coil Allocation Problem (CCAP). Both of these problems happen in the corrugators, a multistage machine which produces corrugated cardboard. The MCWCP appears from the necessity to minimize changes of weight and corrugator rolls during the production process of the bulletins, since each one brings the specific layers’s weight of the sheets, besides the kind of wave put in the middle. The sequence of bulletins impact in the number of weight changes in the coil holders and if there will be corrugating rollers’s exchange for two following bulletins. The gramature’s exchanges impact in the costs of transportation and the corrugating rollers exchange causes lost in the productivity. We propose four whole programming models capable of integrating both considerations. The CCAP integrates many considerations related to the coils’s allocation on the corrugators, for example, the minimization of the non-usable leftovers and the amount of partial consumption, factors which influence directly on the production’s costs. A whole new mist linear model is proposed, determined which coil on the corrugators are going to be used in each coil holder. Besides this, we propose a sequel strategy for the coils in each coil holder, avoiding stops on the corrugators. A series of computation tests using instances created based on real data were made. The results indicate that the models were efficient in solving the problems.

abstract: Traditional deterministic reserve requirements rely on ad-hoc, rule of thumb methods to determine adequate reserve in order to ensure a reliable unit commitment. Since congestion and uncertainties exist in the system, both the quantity and the location of reserves are essential to ensure system reliability and market efficiency. The modeling of operating reserves in the existing deterministic reserve requirements acquire the operating reserves on a zonal basis and do not fully capture the impact of congestion. The purpose of a reserve zone is to ensure that operating reserves are spread across the network. Operating reserves are shared inside each reserve zone, but intra-zonal congestion may block the deliverability of operating reserves within a zone. Thus, improving reserve policies such as reserve zones may improve the location and deliverability of reserve. As more non-dispatchable renewable resources are integrated into the grid, it will become increasingly difficult to predict the transfer capabilities and the network congestion. At the same time, renewable resources require operators to acquire more operating reserves. With existing deterministic reserve requirements unable to ensure optimal reserve locations, the importance of reserve location and reserve deliverability will increase. While stochastic programming can be used to determine reserve by explicitly modelling uncertainties, there are still scalability as well as pricing issues. Therefore, new methods to improve existing deterministic reserve requirements are desired. One key barrier of improving existing deterministic reserve requirements is its potential market impacts. A metric, quality of service, is proposed in this thesis to evaluate the price signal and market impacts of proposed hourly reserve zones. Three main goals of this thesis are: 1) to develop a theoretical and mathematical model to better locate reserve while maintaining the deterministic unit commitment and economic dispatch structure, especially with the consideration of renewables, 2) to develop a market settlement scheme of proposed dynamic reserve policies such that the market efficiency is improved, 3) to evaluate the market impacts and price signal of the proposed dynamic reserve policies. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015