Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-05T11:34:30Z No. of bitstreams: 1 TeseCFB.pdf: 7265467 bytes, checksum: 30543ef140945c783d91cea9b4431c1c (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2017-01-16T12:56:55Z (GMT) No. of bitstreams: 1 TeseCFB.pdf: 7265467 bytes, checksum: 30543ef140945c783d91cea9b4431c1c (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2017-01-16T12:57:02Z (GMT) No. of bitstreams: 1 TeseCFB.pdf: 7265467 bytes, checksum: 30543ef140945c783d91cea9b4431c1c (MD5) / Made available in DSpace on 2017-01-16T12:57:09Z (GMT). No. of bitstreams: 1 TeseCFB.pdf: 7265467 bytes, checksum: 30543ef140945c783d91cea9b4431c1c (MD5) Previous issue date: 2016-10-14 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This thesis proposes to evaluate the effect of transfer batch size on lead time reduction in flow shop environments (balanced and unbalanced, with a bottleneck). In order to achieve this objective, Design Science was used as a research method, in which a static simulation model is proposed and several scenarios are analyzed and evaluated in relation to important Production Management theories. The model proposed to represent a flow shop uses the Factory Physics equations (HOPP; SPEARMAN, 2008) e considers the following shop-floor variables: i) the average setup time; ii) average defect rate; iii) mean time between failures; iv) mean time to repair the machine; v) variability in processing time; vi) variability of the time between arrivals of orders and vii) transfer batch size. The results demonstrate that for both balanced and unbalanced environment, transfer batch size has little effect on lead time, when operating with a process batch size away from optimal batch size (minimum point of the lead time - lot size curve proposed by Karmarkar et al. (1985)). To get a good lead time performance, it is first necessary to reduce process batch size before making efforts to reduce transfer batch. For an unbalanced environment, reducing process batch size only at the bottleneck, coupled to transfer batch size reduction across the flow shop, provided a lead time reduction on the order of 30%, while the remainder flow shop operated with large process batches. In such configuration, the contribution from setup time reduction at the bottleneck machine has generated a small effect on the lead time performance considering the parameters used in this work. / Esta tese se propõe a avaliar o efeito do tamanho do lote de transferência na redução do lead time em ambientes flow shop (balanceado e não balanceado, com a presença de um recurso gargalo). Para atingir tal objetivo, foi utilizado como método de pesquisa o Design Science, no qual um modelo de simulação estático é proposto e diversos cenários são analisados e avaliados em relação a grandes teorias da Gestão da Produção. O modelo aqui proposto para representar um flow shop utiliza as equações do Factory Physics (HOPP; SPEARMAN, 2008) e considera as seguintes variáveis de chão-de-fábrica: i) tempo médio de setup; ii) taxa média de defeitos; iii) tempo médio entre falhas; iv) tempo médio de reparo da máquina; v) variabilidade do tempo de processamento; vi) variabilidade do tempo entre as chegadas de ordens e vii) tamanho do lote de transferência. Os resultados demonstram que tanto para um ambiente balanceado quanto para um ambiente desbalanceado, o tamanho do lote de transferência tem pouco efeito no lead time, quando se opera com um tamanho de lote de produção longe do tamanho de lote ótimo (ponto mínimo da curva lead time – tamanho de lote de produção, proposta por Karmarkar et al. (1985)). Para se obter um bom desempenho em relação ao lead time, é preciso primeiramente reduzir o tamanho do lote de produção, antes de se empreender esforços para a redução do lote de transferência. Em relação a um ambiente desbalanceado, a redução do tamanho do lote de produção apenas no recurso gargalo, aliada à redução do tamanho do lote de transferência em toda a linha, proporcionou uma redução no lead time da ordem de 30%, quando o restante da linha operava com grandes lotes de produção. Nessa configuração, a contribuição da redução do tempo de setup da máquina gargalo gerou um efeito pequeno na redução do lead time, para os parâmetros utilizados nesse trabalho.

Re-entrant permutation flow shop problems occur in practical applications such as wafer manufacturing, paint shops, mold and die processes and textile industry. A re-entrant material flow means that the production jobs need to visit at least one working station multiple times. A comprehensive review gives an overview of the literature on re-entrant scheduling. The influence of missing operations received just little attention so far and splitting the jobs into sublots was not examined in re-entrant permutation flow shops before. The computational complexity of makespan minimization in re-entrant permutation flow shop problems requires heuristic solution approaches for large problem sizes. The problem provides promising structural properties for the application of a variable neighborhood search because of the repeated processing of jobs on several machines. Furthermore the different characteristics of lot streaming and their impact on the makespan of a schedule are examined in this thesis and the heuristic solution methods are adjusted to manage the problem’s extension.

This research is concerned with the development of efficient solutions to various problems that arise in the flow-shop environments which utilize lot-streaming. Lot streaming is a commonly used process of splitting production lots into sublots and, then, of scheduling the sublots in an overlapping fashion on the machines, so as to expedite the progress of orders in production and to improve the overall performance of the production system. The different lot-streaming problems that arise in various flow-shop environments have been divided into two categories, single-lot problems and multiple-lot problems. Further classification of the multiple-lot problems into the lot streaming sequencing problem (LSSP) and the flow-shop lot-streaming (FSLS) problem is made in this work. This classification is motivated by the occurrence of these problems in the industry. Several variants of these problems are addressed in this research. In agreement with numerous practical applications, we assume sublots of equal sizes. It turns out that this restriction paves the way to the relaxation of several typical limitations of current lot-streaming models, such as assumption of negligible transfer and setup times or consideration of only the makespan criterion. For the single-lot problem, a goal programming (GP) approach is utilized to solve the problem for a unified cost objective function comprising of the makespan, the mean flow time, the average work-in-process (WIP), and the setup and handling related costs. A very fast optimal solution algorithm is proposed for finding the optimal number of sublots (and, consequently, the sublot size) for this unified cost objective function in a general m-machine flow shop. For the more complicated multiple-lot problem, a near-optimal heuristic for the solution of the LSSP is developed. This proposed heuristic procedure, referred to as the Bottleneck Minimal Idleness (BMI) heuristic, identifies and employs certain properties of the problem that are irregular in traditional flow-shop problems, particularly the fact that the sublot sizes eminating from the same lot type and their processing times (on the same machines) are identical. The BMI heuristic attempts to maximize the time buffer prior to the bottleneck machine, thereby minimizing potential bottleneck idleness, while also looking-ahead to sequence the lots with large remaining process time earlier in the schedule. A detailed experimental study is performed to show that the BMI heuristic outperforms the Fast Insertion Heuristic (the best known heuristic for flow-shop scheduling), when modified for Lot Streaming (FIHLS) and applied to the problem on hand. For the FSLS problem, several algorithms are developed. For the two-machine FSLS problem with an identical sublot-size for all the lots, an optimal pseudo-polynomial solution algorithm is proposed. For all practical purposes (i.e., even for very large lot sizes), this algorithm is very fast. For the case in which the sublot-sizes are lot-based, optimal and heuristic procedures are developed. The heuristic procedure is developed to reduce the complexity of the optimal solution algorithm. It consists of a construction phase and an improvement phase. In the construction phase, it attempts to find a near-optimal sequence for the lots and then, in the improvement phase, given the sequence, it attempts to optimize the lot-based sublot-sizes of each of the lots. Extensions of the solution procedures are proposed for the general m-machine FSLS problem. A comprehensive simulation study of a flow shop system under lot streaming is conducted to support the validity of the results and to demonstrate the effectiveness of the heuristic procedures. This study clearly indicates that, even in dynamic practical situations, the BMI rule, which is based on the proposed BMI heuristic, outperforms existing WIP rules, commonly used in industry, in scheduling a flow-shop that utilizes lot streaming. With respect to the primary performance measure - cycle time (or MFT) - the BMI rule demonstrates a clear improvement over other WIP rules. It is further shown that it also outperforms other WIP rules with respect to the output variability measure, another important measure in flow-shop systems. The effects of several other factors, namely system randomness, system loading, and bottleneck-related (location and number), in a flow-shop under lot streaming, are also reported. / Ph. D.

[ES] En esta Tesis Doctoral se aborda el problema del taller de flujo de permutación considerando recursos adicionales renovables, que es una versión más realista del clásico problema de taller de flujo de permutación, muy estudiado en la literatura. La inclusión de los recursos ayuda a acercar el mundo académico-científico al mundo real de la industria. Se ha realizado una completa revisión bibliográfica que no se ha limitado a problemas del taller de flujo, sino que han revisado problemas similares del ámbito de scheduling que consideren recursos. En esta revisión, no se han encontrado en la literatura artículos para el problema concreto que se estudia en esta tesis. Por ello, la aportación principal de esta Tesis Doctoral es el estudio por primera vez de este problema y la propuesta y adaptación de métodos para su resolución. Inicialmente, el problema se modeliza a través de un modelo de programación lineal entera mixta (MILP). Dada la complejidad del problema, el MILP es capaz de resolver instancias de un tamaño muy pequeño. Por ello, es necesario adaptar, diseñar e implementar heurísticas constructivas y metaheurísticas para obtener buenas soluciones en un tiempo de computación razonable. Para evaluar la eficacia y eficiencia de los métodos propuestos, se generan instancias de problemas partiendo de los conjuntos más utilizados en la literatura para el taller de flujo de permutación. Se utilizan estas instancias propuestas tanto para calibrar los distintos métodos como para evaluar su rendimiento a través de experimentos computacionales masivos. Los experimentos muestran que las heurísticas propuestas son métodos sencillos que consiguen soluciones factibles de una forma muy rápida. Para mejorar las soluciones obtenidas con las heurísticas y facilitar el movimiento a otros espacios de soluciones, se proponen tres metaheurísticas: un método basado en búsqueda local iterativa (ILS), un método voraz iterativo (IG) y un algoritmo genético con búsqueda local (HGA). Todos ellos utilizan las heurísticas propuestas más eficaces como solución o soluciones iniciales. Las metaheurísticas obtienen las mejores soluciones utilizando tiempos de computación razonables, incluso para las instancias de mayor tamaño. Todos los métodos han sido implementados dentro de la plataforma FACOP (Framework for Applied Combinatorial Optimization Problems). Dicha plataforma es capaz de incorporar nuevos algoritmos de optimización para problemas de investigación operativa relacionados con la toma de decisiones de las organizaciones y está diseñada para abordar casos reales en empresas. El incorporar en esta plataforma todas las metodologías propuestas en esta Tesis Doctoral, acerca el mundo académico al mundo empresarial. / [CA] En aquesta Tesi Doctoral s'aborda el problema del taller de flux de permutació considerant recursos addicionals renovables, que és una versió més realista del clàssic problema de taller de flux de permutació, molt estudiat a la literatura. La inclusió dels recursos ajuda a apropar el món acadèmic-científic al món real de la indústria. S'ha realitzat una revisió bibliogràfica completa que no s'ha limitat a problemes del taller de flux, sinó que ha revisat problemes similars de l'àmbit de scheduling que considerin recursos. En aquesta revisió, no s'ha trobat a la literatura articles per al problema concret que s'estudia en aquesta tesi. Per això, l'aportació principal d'aquesta Tesi Doctoral és l'estudi per primera vegada d'aquest problema i la proposta i l'adaptació de mètodes per resoldre'ls. Inicialment, el problema es modelitza mitjançant un model de programació lineal sencera mixta (MILP). Donada la complexitat del problema, el MILP és capaç de resoldre instàncies d'un tamany molt petita. Per això, cal adaptar, dissenyar i implementar heurístiques constructives i metaheurístiques per obtenir bones solucions en un temps de computació raonable. Per avaluar l'eficàcia i l'eficiència dels mètodes proposats, es generen instàncies de problemes partint dels conjunts més utilitzats a la literatura per al taller de flux de permutació. S'utilitzen aquestes instàncies proposades tant per calibrar els diferents mètodes com per avaluar-ne el rendiment a través d'experiments computacionals massius. Els experiments mostren que les heurístiques proposades són mètodes senzills que aconsegueixen solucions factibles de manera molt ràpida. Per millorar les solucions obtingudes amb les heurístiques i facilitar el moviment a altres espais de solucions, es proposen tres metaheurístiques: un mètode basat en cerca local iterativa (ILS), un mètode voraç iteratiu (IG) i un algorisme genètic híbrid (HGA). Tots ells utilitzen les heurístiques proposades més eficaces com a solució o solucions inicials. Les metaheurístiques obtenen les millors solucions utilitzant temps de computació raonables, fins i tot per a les instàncies més grans. Tots els mètodes han estat implementats dins de la plataforma FACOP (Framework for Applied Combinatorial Optimization Problems). Aquesta plataforma és capaç d'incorporar nous algorismes d'optimització per a problemes de recerca operativa relacionats amb la presa de decisions de les organitzacions i està dissenyada per abordar casos reals a empreses. El fet d'incorporar en aquesta plataforma totes les metodologies proposades en aquesta Tesi Doctoral, apropa el món acadèmic al món empresarial. / [EN] In this Doctoral Thesis, the permutation flowshop problem is addressed considering additional renewable resources, which is a more realistic version of the classic permutation flowshop problem, widely studied in the literature. The inclusion of resources helps to bring the academic-scientific world closer to the real world of industry. A complete bibliographic review has been carried out that has not been limited to flow shop problems, but has reviewed similar problems in the scheduling field that consider resources. In this review, no articles have been found in the literature for the specific problem studied in this thesis. Therefore, the main contribution of this Doctoral Thesis is the study for the first time of this problem and the proposal and adaptation of methods for its resolution. Initially, the problem is modeled through a mixed integer linear programming (MILP) model. Given the complexity of the problem, the MILP is capable of solving very small instances. Therefore, it is necessary to adapt, design and implement constructive heuristics and metaheuristics to obtain good solutions in a reasonable computation time. In order to evaluate the effectiveness and efficiency of the proposed methods, problem instances are generated starting from the sets most used in the literature for the permutation flowshop. These proposed instances are used both to calibrate the different methods and to evaluate their performance through massive computational experiments. Experiments show that proposed heuristics are simple methods that achieve feasible solutions very quickly. To improve the solutions obtained with the heuristics and facilitate movement to other solution spaces, three metaheuristics are proposed: a method based on iterated local search (ILS), an iterative greedy method (IG) and a hybrid genetic algorithm (HGA). All of them use the most effective proposed heuristics as initial solution or solutions. Metaheuristics get the best solutions using reasonable computation times, even for the largest instances. All the methods have been implemented within the FACOP platform (Framework for Applied Combinatorial Optimization Problems). Said platform is capable of incorporating new optimization algorithms for operational research problems related to decision-making in organizations and it is designed to address real cases in companies. Incorporating in this platform all the methodologies proposed in this Doctoral Thesis, brings the academic world closer to the business world. / Alfaro Fernández, P. (2023). Inteligencia computacional en la programación de la producción con recursos adicionales [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/198891

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.

In this work, we address a variety of problems with applications to `ethanol production from biomass', `agile manufacturing' and `mass customization' domains. Our motivation stems from the potential use of biomass as an alternative to non-renewable fuels, the prevalence of `flexible manufacturing systems', and the popularity of `mass customization' in today's highly competitive markets. Production scheduling and design and optimization of logistics network mark the underlying topics of our work. In particular, we address three problems, Biomass Logistics Problem, Hybrid Flow Shop Scheduling Problem, and Stochastic Demand Assembly Job Scheduling Problem. The Biomass Logistics Problem is a strategic cost analysis for setup and operation of a biomass supply chain network that is aimed at the production of ethanol from switchgrass. We discuss the structural components and operations for such a network. We incorporate real-life GIS data of a geographical region in a model that captures this problem. Consequently, we develop and demonstrate the effectiveness of a `Nested Benders' based algorithm for an efficient solution to this problem. The Hybrid Flow Shop Scheduling Problem concerns with production scheduling of a lot over a two-stage hybrid flow shop configuration of machines, and is often encountered in `flexible manufacturing systems'. We incorporate the use of `lot-streaming' in order to minimize the makespan value. Although a general case of this problem is NP-hard, we develop a pseudo-polynomial time algorithm for a special case of this problem when the sublot sizes are treated to be continuous. The case of discrete sublot sizes is also discussed for which we develop a branch-and-bound-based method and experimentally demonstrate its effectiveness in obtaining a near-optimal solution. The Stochastic Demand Assembly Job Scheduling Problem deals with the scheduling of a set of products in a production setting where manufacturers seek to fulfill multiple objectives such as `economy of scale' together with achieving the flexibility to produce a variety of products for their customers while minimizing delivery lead times. We design a novel methodology that is geared towards these objectives and propose a Lagrangian relaxation-based algorithm for efficient computation. / Doctor of Philosophy / In this work, we organize our research efforts in three broad areas - Biomass Supply Chain, Hybrid Flow Shop, and Assembly Job Shop, which are separate in terms of their application but connected by scheduling and logistics as the underlying functions. For each of them, we formulate the problem statement and identify the challenges and opportunities from the viewpoint of mathematical decision making. We use some of the well known results from the theory of optimization and linear algebra to design effective algorithms in solving these specific problems within a reasonable time limit. Even though the emphasis is on conducting an algorithmic analysis of the proposed solution methods and in solving the problems analytically, we strive to capture all the relevant and practical features of the problems during formulation of each of the problem statement, thereby maintaining their applicability. The Biomass Supply Chain pertains to the production of fuel grade ethanol from naturally occurring biomass in the form of switchgrass. Such a system requires establishment of a supply chain and logistics network that connects the production fields at its source, the intermediate points for temporary storage of the biomass, and bio-energy plant and refinery at its end for conversion of the cellulosic content in the biomass to crude oil and ethanol, respectively. We define the components and operations necessary for functioning of such a supply chain. The Biomass Logistics Problem that we address is a strategic cost analysis for setup and operation of such a biomass supply chain network. We focus our attention to a region in South Central Virginia and use the detailed geographic map data to obtain land use pattern in the region. We conduct survey of existing literature to obtain various transportation related cost factors and costs associated with the use of equipment. Our ultimate aim here is to understand the feasibility of running a biomass supply chain in the region of interest from an economic standpoint. As such, we represent the Biomass Logistics Problem with a cost-based optimization model and solve it in a series of smaller problems. A Hybrid Flow Shop (HFS) is a configuration of machines that is often encountered in the flexible manufacturing systems, wherein a particular station of machines can execute processing of jobs/tasks simultaneously. In our work, we approach a specific type of HFS, with a single machine at the first stage and multiple identical machines at the second stage. A batch or lot of jobs/items is considered for scheduling over such an HFS. Depending upon the area of application, such a batch is either allowed to be split into continuous sections or restricted to be split in discrete sizes only. The objective is to minimize the completion time of the last job on its assigned machine at the second stage. We call this problem, Hybrid Flow Shop Scheduling Problem, which is known to be a hard problem in literature. We aim to derive the results which will reduce the complexity of this problem, and develop both exact as well as heuristic methods in order to obtain near-optimal solution to this problem. An Assembly Job Shop is a variant of the classical Job Shop which considers scheduling a set of assembly operations over a set of assembly machines. Each operation can only be started once all the other operations in its precedence relationship are completed. Assembly Job Shop are at the core of some of the highly competitive manufacturing facilities that are principled on the philosophy of Mass Customization. Assuming an inherent nature of demand uncertainty, this philosophy aims to achieve ‘economy of scale’ together with flexibility to produce a variety of products for the customers while minimizing the delivery lead times simultaneously. We incorporate some of these challenges in a concise framework of production scheduling and call this problem as Stochastic Demand Assembly Job Scheduling Problem. We design a novel methodology that is geared towards achieving the set objectives and propose an effective algorithm for efficient computation.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.

由於網際網路的發展，使得全球環境變遷，競爭越來越激烈，企業必須面臨快速的需求變化，以及訂單履行時間縮短的問題，因此如何有效的利用生產規劃和現場排程來幫助企業達到較高的訂單達成率和即時反應現場產能一直是製造業努力的目標。 在排程的問題中，用派工法則來解決排程問題的工廠類型，主要集中在零工式生產系統及流程式生產系統，而進一步加入平行機器概念，即是彈性零工式生產及彈性流程式生產。而現在許多的服務業也都是屬於彈性流程式生產的模式，而且還具有迴流(recirculation)之性質，而之前使用在不具迴流性質之彈性流程式生產的派工法則，在具有迴流性質之彈性流程式生產中是否仍然可以表現良好，是值得探討的。然而更進一步在此具有迴流性質之彈性流程式生產中加入多工的性質，使工作可以被兩個或兩個以上的機器或操作人員進行處理，則運用哪個派工法則讓機器或操作人員選擇工作來進行處理，可以使得選定的目標值有良好的表現，是相當值得研究之問題。 / As information technology advances, whole world environmental trend and the competition is more and more intense. The enterprise must face faster demand changes and the problem of shorter order fulfillment. Therefore, how to apply efficient production planning and shop floor scheduling to attain a better order fulfillment and real time production of shop floor capacity is the goal enterprises strive toward. The shop floor scheduling problems using dispatching rules to solve are focus on job shop scheduling problems and flow shop scheduling problems. Moreover, those problems adding the concept of parallel machine will change into flexible job shop scheduling problems and flexible flow shop scheduling problems. Many service industries also belong to this type. In addition, those service industries’ processes also contain the important characteristic of recirculation. Now, there are two problems I would like to solve. First, Whether the dispatching rules which can get good results in flexible flow shop scheduling problems will also get good results in flexible flow shop scheduling problems with recirculation. Second, I add the characteristic of parallel machine into my problem, so it means jobs in the process can be operated by two or more workers. Therefore, which dispatching rule will get better results based on chosen achievement targets in the problem is very interesting to research.

Pour la résolution de problèmes d'ordonnancement d'ateliers de type flow-shop en industries pharmaceutiques et d'ateliers de type job-shop flexible, deux méthodes d'optimisation ont été développées : une méthode utilisant les algorithmes génétiques dotés d'un nouveau codage proposé et une méthode d'optimisation par essaim particulaire modifiée pour être exploitée dans le cas discret. Les critères retenus dans le cas de lignes de conditionnement considérées sont la minimisation des coûts de production ainsi que des coûts de non utilisation des machines pour les problèmes multi-objectifs relatifs aux industries pharmaceutiques et la minimisation du Makespan pour les problèmes mono-objectif des ateliers job-shop flexibles.Ces méthodes ont été appliquées à divers exemples d'ateliers de complexités distinctes pour illustrer leur mise en œuvre. L'étude comparative des résultats ainsi obtenus a montré que la méthode basée sur l'optimisation par essaim particulaire est plus efficace que celle des algorithmes génétiques, en termes de rapidité de la convergence et de l'approche de la solution optimale