Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura. / In this work we approach the permutational flow shop scheduling problem with more than two machines. We restrict the study to the case where all the jobs have a common and restrictive due date, and where the objective is to minimize the total sum of the earliness and tardiness of jobs relative to the due date. A static and deterministic environment is also assumed. If there are solutions with the same cost, we prefer those that involve less buffer time between each machine. Due to the difficulty of solving the problem, even for small instances (the problem belongs to the NP-hard class), we present a heuristic approach to dealing with it, which is based on local search and makes use of a linear algorithm to assign conclusion times to the jobs on the last machine. This algorithm is based on some analytical properties inherent to optimal solutions. In addition, a mathematical formulation of the problem in mixed integer linear programming (MILP) was developed that will validate the effectiveness of the approach. We also examined the performance of our heuristics with benchmarks and compared our results with those obtained in the literature.

<p>This thesis contains two parts. In the first part, which contains Chapter 2 and Chapter 3, we consider scheduling problems with learning effect and time-dependent processing time on a single machine. In Chapter 2, we investigate the earliness-tardiness objective, as well as the objective without due date assignment consideration. By reducing them to a special linear assignment problem, we solve them in near-linear time. As a consequence, we improve the time complexity for some previous algorithms for scheduling problems with learning effect and/or time-dependent processing time. In Chapter 3, we investigate the total number of tardy jobs objective. By reducing them to a linear assignment problem, we solve them in polynomial time. For some important special cases, where there is only learning effect OR time-dependent processing time, we reduce the time complexity to quadratic time. In the second part, which contains Chapter 4 and Chapter 5, we investigate the bicriteria scheduling problems in a supply chain. We separate the objectives in two parts, where the delivery cost is one of them. We present efficient algorithms to identify all the Pareto-optimal solutions for various scenarios. In Chapter 4, we study the cases without due date assignment; while in Chapter 5 we study the cases with due date assignment consideration.</p>

The Lack of Homogeneity in the Product (LHP) appears in productive processes with raw materials, which directly stem from nature and/or production processes with operations that confer heterogeneity to the characteristics of the outputs obtained, even when the inputs used are homogeneous. LHP appears in different sectors such as ceramic tile, horticulture, marble, snacks, among others. LHP becomes a managerial problem when customers require to be served with homogeneous product. Supply chains responsible to provide homogeneous product face the need to include classification activities in their productive processes to obtain sub-lots of homogeneous product. Due to the inherent LHP uncertainty, these homogeneous sub-lots will not be known until the product have been produced and classified. An improper management of the LHP can have a very negative impact on the customers' satisfaction due to inconsistencies in the answer to their requirements and also on the Supply Chain's efficiency. The Order Promising Process (OPP) appears as a key element for properly managing the LHP in order to ensure the matching of uncertain homogeneous supply with customer order proposals. The OPP refers to the set of business activities that are triggered to provide a response to the orders from customers. These activities are related to the acceptance/rejection decision, and to set delivery dates. For supply chains affected by the LHP, the OPP must consider the homogeneity as another requirement in the answer to the orders. Besides, due to the LHP inherent uncertainty, discrepancies between the real and planned homogeneous quantities might provoke that previously committed orders cannot be served. The Shortage Planning (SP) process intends to find alternatives in order to minimise the negative impact on customers and the supply chain. Considering LHP in the OPP brings a set of new challenging features to be addressed. The conventional approach of assuming homogeneity in the product for the master production schedule (MPS) and the quantities Available-To-Promise (ATP) derived from it is no longer adequate. Instead, both the MPS and ATP should be handled in terms of homogeneous sub-lots. Since the exact quantity of homogeneous product from the planned lots in the MPS is not exactly known until the classification activities have been performed, the ATP also inherits this uncertainty, bringing a new level of complexity. Non-homogeneous product cannot be accumulated in order to fulfil future incoming orders. Even more, if the product handled is perishable, the homogeneity management becomes considerably more complex. This is because the state of the product is dynamic with time and related variables to it, like quality, price, etc., could change with time. This situation could bring unexpected wasting costs apart from the shortages already mentioned. The perishability factor is itself another source of uncertainty associated to the LHP. This dissertation proposes a conceptual framework and different mathematical programming models and tools, in both deterministic and uncertainty environments, in order to support the OPP and SP under LHP's effect. The aim is to provide a reliable commitment with customer orders looking for a high service level not just in the due date and quantity but also in the homogeneity requirements. The modelling of the characteristics inherent to LHP under deterministic context constitutes itself one of the main contribution of this dissertation. Another novelty consists in the inclusion of uncertainty in the definition of homogeneous sub-lots, their quantities and their dynamic state and value. The uncertainty modelling approach proposed is mainly based on the application of fuzzy set theory and possibility theory. The proposed mathematical models and tools have been validated in real cases of SC, specifically in the ceramic tile sector for non perishables, and in the fruit sector for perishables. The results show a ... / La Falta de Homogeneidad en el Producto (LHP, por sus siglas del inglés ``Lack of Homogeneity in the Product'') aparece en procesos productivos con materias primas que derivan directamente de la naturaleza y/o procesos de producción con operaciones que confieren heterogeneidad a las características de los productos obtenidos, incluso cuando los insumos utilizados son homogéneos. La LHP aparece en diferentes sectores como la cerámica, horticultura, mármol, snacks, entre otros. Se convierte en un problema gerencial cuando los clientes requieren homogeneidad en el producto y las cadenas de suministro enfrentan la necesidad de incluir actividades de clasificación en sus procesos productivos para obtener sub-lotes de producto homogéneo. Debido a la incertidumbre inherente a la LHP, los sub-lotes homogéneos y su cantidad no serán conocidos hasta que el producto haya sido producido y clasificado. Una gestión inadecuada de la LHP puede tener un impacto muy negativo en la satisfacción de los clientes debido a inconsistencias en la respuesta a sus requerimientos y también en la eficacia de la Cadena de Suministro. El Proceso de Comprometer de Pedido (OPP, por sus siglas del inglés ``Order Promising Process'') aparece como un elemento clave para gestionar adecuadamente la LHP, con el fin de asegurar la coincidencia entre el suministro incierto de producto homogéneo y las propuestas de pedido del cliente. El OPP se refiere al conjunto de actividades empresariales realizadas para proporcionar una respuesta a las órdenes de los clientes. Estas actividades están relacionadas con las decisiones de aceptación/rechazo, y establecimiento de fechas de entrega para las órdenes del cliente. En las cadenas de suministro afectadas por la LHP, el OPP debe considerar la homogeneidad como otro requisito adicional en la respuesta a los pedidos. Además, debido a la incertidumbre intrínseca de la LHP, las discrepancias entre las cantidades homogéneas reales y planificadas podrían provocar que las órdenes comprometidas anteriormente no puedan ser completadas debido a la escasez de producto. El proceso de planificación de la escasez (SP, por sus siglas del inglés "Shortage Planning") se encarga de encontrar alternativas para minimizar este impacto negativo en los clientes y la cadena de suministro. Considerar la LHP dentro del OPP implica un conjunto nuevo de características desafiantes que deben ser abordadas. El enfoque convencional de asumir la homogeneidad en el producto para el programa maestro de producción (MPS, por sus siglas del inglés "Master Production Schedule") y las cantidades disponibles a comprometer (ATP, por sus siglas del inglés "Available-To-Promise") derivadas de él, no es adecuado. En cambio, tanto el MPS como el ATP deben manejarse en términos de sub-lotes homogéneos. Dado que la cantidad exacta de producto homogéneo de los lotes previstos en el MPS no se sabe exactamente hasta que se han realizado las actividades de clasificación, el ATP también hereda esta incertidumbre, trayendo un nuevo nivel de complejidad. El producto no homogéneo no se puede acumular para satisfacer futuras órdenes entrantes. Más aún, si el producto manipulado es perecedero, el manejo de la homogeneidad se vuelve mucho más complejo. Esto se debe a que el estado del producto es dinámico en el tiempo, y variables relacionadas como calidad, precio, etc., podrían también cambiar con el tiempo. Esta situación puede provocar costos inesperados de desperdicio aparte de la escasez ya mencionada. El factor de perecedero es en sí mismo otra fuente de incertidumbre asociada a la LHP. Esta disertación propone un marco conceptual y diferentes modelos y herramientas de programación matemática, tanto en entornos deterministas como de incertidumbre, para apoyar al OPP y SP considerando el efecto de LHP. El objetivo es proporcionar un compromiso fiable con los pedidos de los clientes en busca de un alto nivel de servicio no s / La Falta d'Homogeneïtat en el Producte (LHP, per les seues sigles de l'anglés ''Lack of Homogeneity in the Product'') apareix en processos productius amb matèries primes que deriven directament de la natura i/o processos de producció amb operacions que conferixen heterogeneïtat a les característiques dels productes obtinguts, fins i tot quan les entrades utilitzades són homogènies . La LHP apareix en diferents sectors com la ceràmica, horticultura, marbre, snacks, entre altres. Es convertix en un problema gerencial quan els clients requereixen homogeneïtat en el producte i les cadenes de subministrament enfronten la necessitat d'incloure activitats de classificació en els seus processos productius per a obtindre sublots de producte homogeni. A causa de la incertesa inherent a la LHP, els sublots homogenis i la seua quantitat no seran coneguts fins que el producte haja sigut produït i classificat. Una gestió inadequada de la LHP pot tindre un impacte molt negatiu en la satisfacció dels clients degut a inconsistències en la resposta als seus requeriments i també en l'eficàcia de la Cadena de Subministrament. El Procés de Comprometre Comandes (OPP, per les seues sigles de l'anglés ''Order Promising Process'') apareix com un element clau per a gestionar adequadament la LHP, a fi d'assegurar la coincidència entre el subministrament incert de producte homogeni i les propostes de comanda del client. L'OPP es refereix al conjunt d'activitats empresarials realitzades per a proporcionar una resposta a les ordres dels clients. Aquestes activitats estan relacionades amb les decisions d'acceptació/rebuig, i establiment de dates de lliurament per a les ordres del client. En les cadenes de subministrament afectades per la LHP, l'OPP ha de considerar l'homogeneïtat com un altre requisit addicional en la resposta a les comandes. A més, a causa de la incertesa intrínseca de la LHP, les discrepàncies entre les quantitats homogènies reals i planificades podrien provocar que les ordres compromeses anteriorment no puguen ser completades a causa de l'escassetat de producte. El procés de planificació de l'escassetat (SP, per les seues sigles de l'anglés "Shortage Planning") s'encarrega de trobar alternatives per a minimitzar aquest impacte negatiu en els clients i en la cadena de subministrament. Considerar la LHP dins de l'OPP implica un conjunt nou de característiques desafiants que han de ser abordades. L'enfocament convencional d'assumir l'homogeneïtat en el producte per al programa mestre de producció (MPS, per les seues sigles de l'anglés "Master Production Schedule") i les quantitats disponibles a comprometre (ATP, per les seues sigles de l'anglés "Available-To-Promise") derivades d'ell, no és adequat. En canvi, tant el MPS com l'ATP han de manejar-se en termes de sublots homogenis. Atés que la quantitat exacta de producte homogeni dels lots previstos en el MPS no se sap exactament fins que s'han realitzat les activitats de classificació, l'ATP també hereta aquesta incertesa, portant un nou nivell de complexitat. El producte no homogeni no es pot acumular per a satisfer futures ordees entrants. Més encara, si el producte manipulat és perible, el maneig de l'homogeneïtat es torna molt més complex. Açò es deu al fet que l'estat del producte és dinàmic en el temps, i variables relacionades com qualitat, preu, etc., podrien també canviar amb el temps. Aquesta situació pot provocar costos inesperats de rebuig a banda de l'escassetat ja esmentada. El factor de perible és en si mateix un altra font d'incertesa associada a la LHP. Aquesta dissertació proposa un marc conceptual i diferents models i eines de programació matemàtica, tant en entorns deterministes com d'incertesa, per a recolzar a l'OPP i SP considerant l'efecte de LHP. L'objectiu és proporcionar un compromís fiable amb les comandes dels clients a la recerca d'un alt nivell de servei no sols en la data i la quantitat esperades, s / Grillo Espinoza, H. (2017). Advanced methods and models in uncertainty for the order promising process in supply chain characterized by the lack of homogeneity in product [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/91110 / TESIS

The purpose of this thesis is to develop a model that will guide a company towards a decision of whether to change the current due date of work orders or not. The model will help the company to reveal the technical and financial factors that will be affected and how these factors can be assessed. After accomplishing a thorough literature review, we found no existing practical models in this specific area. We developed a model to cover this gap in the existing theories. A case study approach was used to test the developed model on our case company Elitfönster in Lenhovda who manufactures windows. We applied our model at the processing department and the change concerned going from a weekly to a daily due date of work orders. The technical factors that would be affected by the change of the due date are; setup times, lead time and output of components. The financial factors that will be affected are the tied-up capital and the manning. We found that a change could not be carried through without a purchase of an extra plane. The model also showed that the financial benefits that the change generated could not surpass the costs that an extra plane would cause. Thereby, our recommendations to the case company are to keep the current due date of work orders until the rest of the company can handle the extra components that can be produced after the change. / Syftet med denna uppsats är att utveckla en modell som ska vägleda ett företag mot ett beslut om man ska ändra den nuvarande tidpunkt när en arbetsorder ska vara färdigställd, eller inte. Modellen kommer att hjälpa företaget att påvisa de tekniska och finansiella faktorer som kommer att påverkas och hur dessa kan bedömas. Efter att ha gjort en grundlig litteraturstudie kunde vi inte hitta några existerande modeller inom detta specifika område. Vi utvecklade en modell för att täcka denna brist i den existerande teorin. Vi använde oss av en fallstudie för att testa vår utvecklade modell på Elitfönster i Lenhovda som tillverkar fönster. Vi applicerade vår modell på maskinverkstaden och förändringen handlade om att gå från att färdigställa arbetsorder på en vecka till att färdigställa dem på en dag. De tekniska faktorer som skulle påverkas av en förändring är; ställtiderna, ledtiden och mängden producerade komponenter. De finansiella faktorerna som kommer att påverkas är mängden bundet kapital samt bemanningen. Vi kom fram till att en förändring inte kunde genomföras utan att köpa in en extra hyvel. Modellen visade också att de finansiella fördelarna som en förändring skulle generera inte skulle motsvara de kostnader som den extra hyveln skulle orsaka. Våra rekommendationer till företaget är således att fortsätta med den nuvarande tidpunkt när en arbetsorder ska vara färdigställd tills resten av företaget kan hantera de extra komponenter som skulle kunna bli producerade efter förändringen.

<p>The purpose of this thesis is to develop a model that will guide a company towards a decision of whether to</p><p>change the current due date of work orders or not. The model will help the company to reveal the technical and</p><p>financial factors that will be affected and how these factors can be assessed. After accomplishing a thorough</p><p>literature review, we found no existing practical models in this specific area. We developed a model to cover this</p><p>gap in the existing theories. A case study approach was used to test the developed model on our case company</p><p>Elitfönster in Lenhovda who manufactures windows. We applied our model at the processing department and the</p><p>change concerned going from a weekly to a daily due date of work orders. The technical factors that would be</p><p>affected by the change of the due date are; setup times, lead time and output of components. The financial</p><p>factors that will be affected are the tied-up capital and the manning. We found that a change could not be carried</p><p>through without a purchase of an extra plane. The model also showed that the financial benefits that the change</p><p>generated could not surpass the costs that an extra plane would cause. Thereby, our recommendations to the</p><p>case company are to keep the current due date of work orders until the rest of the company can handle the extra</p><p>components that can be produced after the change.</p> / <p>Syftet med denna uppsats är att utveckla en modell som ska vägleda ett företag mot ett beslut om man ska</p><p>ändra den nuvarande tidpunkt när en arbetsorder ska vara färdigställd, eller inte. Modellen kommer att hjälpa</p><p>företaget att påvisa de tekniska och finansiella faktorer som kommer att påverkas och hur dessa kan bedömas.</p><p>Efter att ha gjort en grundlig litteraturstudie kunde vi inte hitta några existerande modeller inom detta specifika</p><p>område. Vi utvecklade en modell för att täcka denna brist i den existerande teorin. Vi använde oss av en</p><p>fallstudie för att testa vår utvecklade modell på Elitfönster i Lenhovda som tillverkar fönster. Vi applicerade vår</p><p>modell på maskinverkstaden och förändringen handlade om att gå från att färdigställa arbetsorder på en vecka</p><p>till att färdigställa dem på en dag. De tekniska faktorer som skulle påverkas av en förändring är; ställtiderna,</p><p>ledtiden och mängden producerade komponenter. De finansiella faktorerna som kommer att påverkas är</p><p>mängden bundet kapital samt bemanningen. Vi kom fram till att en förändring inte kunde genomföras utan att</p><p>köpa in en extra hyvel. Modellen visade också att de finansiella fördelarna som en förändring skulle generera</p><p>inte skulle motsvara de kostnader som den extra hyveln skulle orsaka. Våra rekommendationer till företaget är</p><p>således att fortsätta med den nuvarande tidpunkt när en arbetsorder ska vara färdigställd tills resten av företaget</p><p>kan hantera de extra komponenter som skulle kunna bli producerade efter förändringen.</p>