This study is undertaken to improve the performance of a Chemotherapy Treatment Unit by increasing the throughput of the clinic and reducing the average patients’ waiting time. In order to achieve this objective, a simulation model of this system is built and several scenarios that target matching the arrival pattern of the patients and resources availability are designed and evaluated. After performing detailed analysis, one scenario proves to provide the best system’s performance. The best scenario determines a rational arrival pattern of the patient matching with the nurses’ availability and can serve 22.5% more patients daily. Although the simulation study shows the way to serve more patients daily, it does not explain how to sequence them properly to minimize the average patients’ waiting time. Therefore, an efficient scheduling algorithm was developed to build a scheduling template that minimizes the total flow time of the system.

Minicell-based manufacturing system is used in identifying best minicell designs. The existing method of minicell design generates best minicell designs by designing and scheduling minicells simultaneously. While in this research designing of minicells and scheduling of jobs in minicells is done separately. This research evaluates the effectiveness of hierarchical approach and compares with simultaneous method. Minicell designs with respect to average flow times and machine capacities and both are identified in a multi-stage flow shop environment. Rules for the extraction of good minicell designs in mass customization manufacturing systems are also established.

Minicells are small manufacturing cells dedicated to an option family and organized in a multi-stage configuration for mass customization manufacturing. Product variants, depending on the customization requirements of each customer, are routed through the minicells as necessary. For successful mass customization, customized products must be manufactured at low cost and with short turn around time. Effective scheduling of jobs to be processed in minicells is essential to quickly deliver customized products. In this research, a genetic algorithm based approach is developed to schedule jobs in a minicell configuration by considering it as a multi-stage flow shop. A new crossover strategy is used in the genetic algorithm to obtain a minimum flow time schedule.

This study is undertaken to improve the performance of a Chemotherapy Treatment Unit by increasing the throughput of the clinic and reducing the average patients’ waiting time. In order to achieve this objective, a simulation model of this system is built and several scenarios that target matching the arrival pattern of the patients and resources availability are designed and evaluated. After performing detailed analysis, one scenario proves to provide the best system’s performance. The best scenario determines a rational arrival pattern of the patient matching with the nurses’ availability and can serve 22.5% more patients daily. Although the simulation study shows the way to serve more patients daily, it does not explain how to sequence them properly to minimize the average patients’ waiting time. Therefore, an efficient scheduling algorithm was developed to build a scheduling template that minimizes the total flow time of the system.

<p>Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance. </p><p>The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.</p><p>The main contributions of the thesis can be placed in one of the following categories.</p><p>1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.</p><p>2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.</p><p>3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.</p><p>4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.</p> / Dissertation

In cellular manufacturing systems, minimization of the completion time has a great impact on the production time, material flow, and productivity. An effective scheduling is crucial to attaining the advantages of cellular manufacturing systems. This dissertation attempts to solve the Flowshop Manufacturing Cell (cellular flowshop) Scheduling Problem with Sequence Dependent Setup Times (FMCSP with SDSTs) considering two performance measures: the total flow time as a mono objective, and the makespan and total flow time combined as a bi-criteria scheduling problem. The proposed problem is known to be the NP-hard problem because of its complexity. Several metaheuristic algorithms based on Genetic Algorithm (GA), Simulated Annealing (SA), and Particle Swarm Optimization (PSO) are developed for scheduling part families as well as jobs within each part family for FMCSP with SDSTs to minimize the total flow time. A local search method based on SA combined with PSO (named as PSO-SA) is proposed to enhance the intensification and improve the quality of the solution obtained by pure PSO. The effectiveness and efficiency of the proposed metaheuristics are evaluated based on the Relative Percentage Deviation (RPD) from its lower bound, and the robustness. Results indicate PSO-SA is performed similar to best available algorithms for small and medium size test problems. Yet, there is a very small deviation from best results for large problems. A Multi-objective Particle Swarm Optimization (MPSO) and a Multi-objective Simulated Annealing (MOSA) Algorithm are further proposed to solve the bi-criteria optimization problem to minimize the total flow time and makespan simultaneously. An improved PSO is combined with Threshold Acceptance (TA) algorithm to improve effectiveness of the proposed MPSO (named as IMPSO-TA) for the convergence of the obtained Pareto Front. The proposed algorithms are evaluated using several Quality Indicators (QI) measures for multiobjective optimization problems. The proposed algorithms can generate approximated Pareto Fronts in a reasonable CPU time. The proposed IMPSO-SA outperforms MOSA algorithm in terms of CPU time and minimizing the objective functions. / October 2015

Since the very beginning of the development of computers they have been used to accelerate the knowledge gain in science and research. Today they are a core part of most research facilities. Especially in natural and technical sciences they are used to simulate processes that would be hard to observe in real world experiments. Together with measurements from such experiments, simulations produce huge amounts of data that have to be analyzed by researchers to gain new insights and develop their field of science.

As the Army transitions to the Army Force Generation (ARFORGEN) deployment cycle, it must adjust its many operations in support of ARFORGEN. Specifically, the Initial Military Training (IMT) must be able to adjust the scheduling of its classes for newly enlisted service members to finish training such that they fulfill Brigade Combat Team (BCT) requirements within their common due windows. We formulate this problem as a lot streaming problem. Lot streaming splits a batch of jobs into sublots,which are then processed over the machines in an overlapping fashion. To schedule classes for the IMT, there are two stages that must be coordinated: Basic Training (BT) and Advanced Individual Training (AIT). For the Army Force Generation problem, the classes are considered as sublots that are streamed from one stage to the next. For this process, the model formulation must address determination of class sizes and scheduling of soldiers and classes at the two stages such that (1) the start times of the soldiers at Stage 2 are greater than their completion times at Stage 1, and (2) the assignment of requisite number of soldiers is made to each BCT, so as to minimize the total flow time. We propose a decomposition-based approach for the solution of this problem. In an effort to decompose the problem, the original lot streaming problem is reformulated such that the master problem selects an optimal combination of schedules for training classes and assigning soldiers to BCTs. A complete schedule selected in the master problem includes the assignments of soldiers to classes in BT, AIT, and their assignments to the BCTs, so as to minimize the total flow time as well as earliness and tardiness for regular Army units. Earliness and Tardiness are defined as the length of the time a soldier waits before and after the due date, respectively, of the BCT to which he or she is assigned. Our decomposition-based method enables solution of larger problem instances without running out of memory, and it affords CPU time reductions when compared with the CPU times required for these problem instances obtained via direct application of CPLEX 12.1. Our investigation into the structure of the problem has enabled further improvement of the proposed decomposition-based method. This improvement is achieved because of a result, which we show, that the first and second-stage scheduling problems need not be solved as one combined subproblem, but rather, they can be solved sequentially, the first stage problem followed by the second stage problem. The combination of Stage 1 and Stage 2 problems as one subproblem creates several additional enumerations of possible schedules the model must generate. By reducing this number of enumerations, the computational effort involved in solving the model reduces significantly, thereby allowing reductions in CPU time. In the Sequential approach, the completion times of soldiers determined at Stage 1 are passed to Stage 2 as bounds on their completion times at Stage 2. We prove that solving the combined subproblem sequentially as two subproblems is optimal when the first stage has no limit on the batch size and the ready times of the soldiers at Stage 1 are the same. For the Army Force Generation problem, we use unequal ready times, and therefore, solving the scheduling problems for the first two stages as sequential subproblems can lead to suboptimal solutions. Our experimental investigation shows efficacy of solving larger-sized problem instances with this method. We also recommend various potential additions to improve the Sequential approach for application to the overall Army problem. We have also demonstrated the use of our methodology to a real-life problem instance. Our methodology results in schedules for IMT with an estimated 28% reduction in mean flow time for soldiers over what is currently experienced in practice. We apply this Sequential approach to various extensions of the problem on hand that pertain to hybrid flow shop and agile manufacturing environments. Results of our computational investigation show the effectiveness of using the Sequential approach over direct solution by CPLEX from the viewpoint of both optimality gap and the CPU time required. In particular, we consider two different model configurations for a hybrid flow shop and three different model configurations for an agile manufacturing facility. / Ph. D.

Em um contexto industrial, a programação da produção tem como objetivo alocar recursos para operações de forma a aumentar a eficiência operacional do processo de fabricação. Esta programação pode ser modelada na forma de problemas de sequenciamento de tarefas, que são resolvidos visando minimizar um determinado critério de desempenho. A aplicação de métodos exatos nestes problemas possibilita encontrar a solução ótima, tanto para aplicação direta como para a validação de métodos heurísticos e metaheurísticas. Entretanto, a literatura mostra que os métodos exatos, tanto a resolução do problema pela modelagem em programação linear-inteira mista como o branch-and-bound, têm sua aplicação restrita à problemas de menores tamanhos. O objetivo deste trabalho é propor novas formulações de limitantes inferiores para a aplicação do branch-and-bound em problemas de flowshop permutacional visando aumentar sua eficiência e aplicabilidade. Os limitantes propostos são avaliados em problemas de flowshop permutacional com tempos de setup dependente da sequência, tendo como critérios de desempenho o tempo de fluxo total e o atraso total. A avaliação da aplicabilidade de cada limitante é feita através do número de nós explorados e o tempo computacional gasto pelo branch-and-bound para resolver problemas de diversos tamanhos. / In an industrial context, production sequencing aims at allocating resources for job processing while increasing manufacturing efficiency. This task can be modelled in the form of scheduling problems, which are solved by minimizing a pre-determined performance criterion. The use of exact methods allows the optimal solution to be found, which can be applied directly in the manufacturing shop or used to validate heuristic and metaheuristic methods. However, the literature shows that MILP and branch-and-bound, both exact methods, are restrained to small-sized scheduling problems. The aim of this project is to propose new lower bound formulations to be used in the branch-and-bound method for permutational flowshop probems, in order to extend its efficiency and applicability. The proposed bounds are tested in permutational flowshop problems with sequence dependent setup times, and using as performance criteria the total flow time and the total tardiness. The evaluation of each lower bounds applicability is done considering the number of explored nodes and the required computational time for the branch-and-bound to solve problem instances of different sizes.

La constante de temps du débit de base (τ) représente le temps moyen pour que l'eau souterraine arrive à la rivière depuis la zone de recharge dans un bassin donné. C’est un élément clé pour simuler le débit de base dans les modèles simples des eaux souterraines, tels qu’ORCHIDEE. τ a été estimée à l’échelle globale à partir d’une solution de l’équation de Boussinesq pour les aquifères libres en pente. τ dépend de la porosité efficace, de la transmissivité, de la pente de l'aquifère et de la densité de drainage (δ). Calculées à partir de bases de données globales, les valeurs de τ sont surestimées par rapport à celles obtenues par analyse des courbes de récession. Une analyse de sensibilité a montré que la transmissivité et δ sont les principales sources d’incertitude de τ. L’extraction d’un nouveau réseau de drainage, qui dépend de la lithologie, du climat, de la pente et des δ observées, a permis d’obtenir des δ conformes aux valeurs observées aux échelles régionales et à la variabilité spatiale. L’utilisation de ces nouvelles δ et la combinaison de deux jeux de données de conductivité hydraulique pour le sol et l’aquifère a réduit τ de deux ordres de grandeur, mais les valeurs calculées restent surestimées. L’utilisation de τ dans le modèle de surface ORCHIDEE a montré une forte sensibilité du débit simulé à l’augmentation de τ, qui dégrade les débits simulés par rapport aux observations. Cette méthodologie nécessite des valeurs plus adaptées de transmissivité et porosité efficace par rapport aux jeux de données globaux actuellement disponibles pour obtenir des valeurs de τ plus proches de celles attendues et qui permettent de reproduire les débits observés. / The base flow time constant (τ) represents the mean amount of time the groundwater takes to reach the stream from the recharge zone in a given watershed. τ is a key element to simulate base flow in simple groundwater models as ORCHIDEE. τ was estimated at global scale based on a solution of the Boussinesq equation for unconfined sloping aquifers. τ depends on the effective porosity, transmissivity, aquifer slope, and drainage density (δ). When estimated from global available datasets, τ results are overestimated when compared to recession analysis results. A sensitivity analysis showed that transmissivity and δ are the main uncertainty sources of τ. A river network extraction based on lithology, climate, slope, and observed δ allowed to obtain δ values close to reference data and spatially variable at regional scale. The use of a new δ and the combination of two hydraulic conductivity datasets of soil and aquifer reduced τ of two orders of magnitude, however the values remained overestimated. The use of τ in ORCHIDEE land surface model showed a strong sensitivity of the river discharge buffer effect to τ, which worsen simulated river discharge when compared to observations. This methodology needs more adequate porosity and transmissivity values when compared to global available datasets that will result in close results to observed river discharge.