Hundreds of steel products need to be scheduled on a single or parallel machine in a steel plant every week. A good feasible schedule may save the company millions of dollars compared to a bad one. Single and parallel machine scheduling are also encountered often in many other industries, making it a crucial research topic for both the process system engineering and operations research communities. Single or parallel machine scheduling can be a challenging combinatorial optimization problem when a large number of jobs are to be scheduled. Each job has unique job characteristics, resulting in different setup times/costs depending on the processing sequence. They also have specific release dates to follow and due dates to meet. This work presents both an exact method using mixed-integer quadratic programming, and an approximate method with metaheuristics to solve real-world large-scale single/parallel machine scheduling problems faced in a steel plant. More than 1000 or 350 jobs are to be scheduled within a one-hour time limit in the single or parallel machine problem, respectively. The objective of the single machine scheduling is to minimize a combined total changeover, total earliness, and total tardiness cost, whereas the objective of the parallel machine scheduling is to minimize an objective function comprising the gaps between jobs before a critical time in a schedule, the total changeover cost, and the total tardiness cost. The exact method is developed to benchmark computation time for a small-scale single machine problem, but is not practical for solving the actual large-scale problem. A metaheuristic algorithm centered on variable neighborhood descent is developed to address the large-scale single machine scheduling with a sliding-window decomposition strategy. The algorithm is extended and modified to solve the large-scale parallel machine problem. Statistical tests, including Student's t-test and ANOVA, are conducted to determine efficient solution strategies and good parameters to be used in the metaheuristics. / Thesis / Master of Applied Science (MASc)

[pt] A exploração e produção (EeP) offshore de óleo e gás envolve várias operações complexas e importantes, como perfuração, avaliação, completação e manutenção de poços. A maioria dessas tarefas requer o uso de sondas, um recurso custoso e escasso que as companhias de petróleo precisam planejar e programar corretamente. Na literatura, este problema é chamado de Programação de Sondas. Todavia, existem poucos estudos relacionados aos poços marítimos e às atividades de perfuração e nenhum destes com funções objetivo e restrições realistas, como orçamento. Por isso, muitas empresas de petróleo têm fortes dificuldades no planejamento das sondas, resultando em grandes custos para elas. Com o objetivo de preencher essa lacuna, esta dissertação estuda um problema de programação de sondas em uma empresa petroleira e propõe um método híbrido para determinar a frota de sondas e seu cronograma, que minimize o orçamento da empresa. Dois modelos de programação matemática – um para minimização das sondas e outro para minimizar seu orçamento com variações da unidade de tempo utilizada (dia ou semana) – e várias heurísticas – usando algoritmos de busca local e variable neighborhood descent (VND) com três estruturas de vizinhança e duas estratégias de busca (first e best improvemment) e métodos construtivos- foram desenvolvidos e testados em duas instâncias (uma pequena e uma grande), baseadas em dados reais da empresa do caso de estudo. As três estruturas de vizinhanças são baseadas em movimentos de insert, uma delas não permite alterar as datas de alocação das tarefas na solução inicial, outra permite adiar tarefas e a última as posterga.Os resultados indicaram a dificuldade no desempenho dos modelos matemáticos nas grandes instâncias e uma forte capacidade das heurísticas para encontrar soluções similares com muito menos esforço computacional. Na instância pequena, o modelo exato para minimizar o orçamento encontrou soluções um pouco melhores que a heurística (diferença de entre 0,4 por cento e 5,6 por cento), embora necessitando de mais esforço computacional, principalmente os modelos com unidades de tempo em dias. Porém, na instância maior, as soluções da programação matemática possuíram altos gap (mais de 11 por cento) e altos tempos computacionais (pelo menos 12 horas), tendo o modelo matemático mais completo sido incapaz de encontrar soluções inteiras viáveis ou limites inferiores depois de mais de um dia rodando. Enquanto isso, as heurísticas foram capazes de encontrar soluções similares ou até melhores (desvios de -6 por cento e 14 por cento em relação a melhor solução exata) em um tempo muito menor, tendo 70 das 156 heurísticas desenvolvidas superado os modelos matemáticos. Além disso, os melhores resultados heurísticos foram utilizando algoritmos de variable neighborhood descent (VND) com estruturas de vizinhanças que realizavam movimentos de insert de tarefas em sondas existentes ou novas e permitiam postergar ou adiantar as tarefas das sondas. A abordagem hibrida foi comparada também com uma abordagem puramente heurística, tendo a primeira obtido melhores resultados. Por fim, os resultados demonstram que o método híbrido proposto combinando o modelo matemático que minimiza o número de sondas com as heurísticas de busca local é uma ferramenta de suporte a decisão rápida e prática, com potencial para reduzir milhões de dólares para as empresas petroleiras do mercado offshore, com capacidade para encontrar cronogramas próximos da solução ótima com pouco esforço computacional, mesmo em instâncias grandes onde a maioria dos métodos exatos é muito complexa e lenta. / [en] The offshore exploration and production (EandP) of Oil and Gas involves several complex and important operations and relies, mostly, in the use of rigs, a scarce and costly resource that oil companies need to properly plan and schedule. In the literature, this decision is called the Rig Scheduling Problem (RSP). However, there is not any study related to offshore wells and drilling activities with realistic objective functions. Aiming to fulfill this gap, this dissertation studies a rig scheduling problem of a real offshore company and proposes a matheuristic approach to determine a rigs fleet and schedule that minimizes the budget. Two mathematical models – one for rigs fleet minimization and another one that minimizes the rigs budget – and several heuristics – using local search (LS) and variable neighborhood descent (VND) algorithms with three neighborhood structures and also constructive methods – were developed and tested in two instances based on real data of the studied company. In the small instance, the programming model found slightly better solutions than the heuristic, despite requiring more computational effort. Nevertheless, in the large instance, the mathematical programming solutions present large gaps (over 11 percent) and an elevated computational time (at least 12 hours), while the heuristics can find similar (or even better) solutions in a shorter time (minutes), having 70 of 156 heuristics outperformed the mathematical models. Last, the matheuristic combination of the simplest mathematical model with the heuristics has found the best known solutions (BKS) of the large instance with a moderate computational effort.

No description available.

本研究將探討非等效平行機台問題中具備順序相依整備時間及不同開始工作時間（Unequal ready-time）之情況，並以最小化總延遲工件權重數為目標值，其目的在改善非等效平行機台問題應用於實際產業中製造環境裡所面對的各項挑戰，如印刷電路板的鑽孔和半導體的測試製程。因本研究欲求解之問題是屬於NP - Hard problems 性質之尋優問題，故利用啟發式方法(heuristics)求解為合適的選擇。此外，本研究計畫開發混合式巨集啟發式方法來求解非等效平行機台問題，主要以禁忌搜尋法為主，在鄰域的搜尋上，也藉由變動鄰域尋優法能夠透過鄰域轉換的機制，進而找出更多好的解。由於啟發式方法對於尋優問題常需花費許多時間來計算才能獲得更好的解，為確保增進求解效率與品質，將針對問題特性開發數種初始解產生法，並也嘗試定義幾個能夠減少尋找鄰近解之鄰域。在後續求解改善的過程中，主要整合變動鄰域(VND)及禁忌(TS)巨集啟發式演算法搜尋最佳解。此外，為了評估本文推導之演算法效能，本研究利用設定之條件隨機產生適量模擬現場狀況的測試情境，進而比較本研究所提出之混合式巨集啟發式方法及標準禁忌搜尋法在不同情境下之表現。 / The problem considered in this paper is a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and with unequal ready times so as to minimize total weighted tardy jobs. These problems can be found in real-life manufacturing environments, such as PCB fabrication drilling operations and semiconductor wafer manufacturing dicing. Since the problems are NP-hard in the strong sense, heuristics are an acceptable practice to finding good solutions. A hybrid meta-heuristics are proposed to solve this scheduling problem. The proposed heuristics belong to a type of solution improvement heuristic; therefore, the heuristics start with an effective initial feasible solution then a meta-heuristic is applied to improve the solution. To enhance both the efficiency and efficacy of the heuristics, several different initial solution generators, based on the characteristics of problems, are developed. The meta-heuristic is a hybrid heuristic integrating the principles of Variable Neighborhood Descent approach (VND) and Tabu Search (TS). In order to evaluate the performance of the proposed heuristics, two sets of large number test scenarios will be designed to simulate practical shop floor problems. Computational experiments will be performed to compare the performance of the proposed heuristics, and a basic tabu search algorithm. The results show the proposed heuristic perform better than the basic tabu search algorithm.

In this thesis, we study three supply chain planning problems. The first two problems fall in the tactical planning level, while the third one falls in the strategic/tactical level. We present a direct application for the first two planning problems in the wind turbines industry. For the third problem, we show how it can be applied to supply chains in the food industry. Many countries and localities have the explicitly stated goal of increasing the fraction of their electrical power that is generated by wind turbines. This has led to a rapid growth in the manufacturing and installation of wind turbines. The globally installed capacity for the manufacturing of different components of the wind turbine is nearly fully utilized. Because of the large penalties for missing delivery deadlines for wind turbines, the effective planning of its supply chain has a significant impact on the profitability of the turbine manufacturers. Motivated by the planning challenges faced by one of the world’s largest manufacturers of wind turbines, we present a comprehensive tactical supply chain planning model for manufacturing of wind turbines in the first part of this thesis. The model is multi-period, multi-echelon, and multi-commodity. Furthermore, the model explicitly incorporates backorder penalties with a general cost structure, i.e., the cost structure does not have to be linear in function of the backorder delay. To the best of our knowledge, modeling-based supply chain planning has not been applied to wind turbines, nor has a model with all the above mentioned features been described in the literature. Based on real-world data, we present numerical results that show the significant impact of the capability to model backorder penalties with general cost structures on the overall cost of supply chains for wind turbines. With today’s rapidly changing global market place, it is essential to model uncertainty in supply chain planning. In the second part of this thesis, we develop a two-stage stochastic programming model for the comprehensive tactical planning of supply chains under supply uncertainty. In the first stage, procurement decisions are made while in the second stage, production, inventory, and delivery decisions are made. The considered supply uncertainty combines supplier random yields and stochastic lead times, and is thus the most general form of such uncertainty to date. We apply our model to the same wind turbines supply chain. We illustrate theoretical and numerical results that show the impact of supplier uncertainty/unreliability on the optimal procurement decisions. We also quantify the value of modeling uncertainty versus deterministic planning. Supplier selection with quantity discounts has been an active research problem in the operations research community. In this the last part of this thesis, we focus on a new quantity discounts scheme offered by suppliers in some industries. Suppliers are selected for a strategic planning period (e.g., 5 years). Fixed costs associated with suppliers’ selection are paid. Orders are placed monthly from any of the chosen suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate all this in a multi-period multi-product multi-echelon supply chain planning problem and develop a mixed integer programming (MIP) model for it. Leading commercial MIP solvers take 40 minutes on average to get any feasible solution for realistic instances of our model. With the aim of getting high-quality feasible solutions quickly, we develop an algorithm that constructs a good initial solution and three other iterative algorithms that improve this initial solution and are capable of getting very fast high quality primal solutions. Two of the latter three algorithms are based on MIP-based local search and the third algorithm incorporates a variable neighborhood Descent (VND) combining the first two. We present numerical results for a set of instances based on a real-world supply chain in the food industry and show the efficiency of our customized algorithms. The leading commercial solver CPLEX finds only a very few feasible solutions that have lower total costs than our initial solution within a three hours run time limit. All our iterative algorithms well outperform CPLEX. The VND algorithm has the best average performance. Its average relative gap to the best known feasible solution is within 1% in less than 40 minutes of computing time.