Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

Underground mining is a complex operation that requires careful planning. The short-term scheduling, which is the scheduling of the tasks involved in the excavation process, is an important part of the planning process. In this master thesis we propose a new method for short-term scheduling of a cut-and-fill mine operated by the mining company Boliden AB. We include a new aspect of the problem by incorporating a priority between the excavation locations of the mine. The priority feature allows the user to control the output of the scheduling and to direct resources to the locations where they are most needed according to the long-term plans. Our solution method consists of two components: a constructive heuristic method that construct a complete solution by solving partial scheduling problems containing subsets of tasks, and a logic-based Benders decomposition scheme for solving these partial problems. The computational performance of the proposed method is evaluated on industrially relevant largescale instances generated from data provided by Boliden. Comparisons are made with applying a constraint programming solver on the complete problem and with replacing the logic-based Benders scheme by applying a constraint programming solver on the partial scheduling problems, respectively. Results show that the heuristic method combined with the logic-based Benders decomposition scheme outperforms the other two methods on all instances.

Logic-based Benders decomposition (LBBD) is a strategy for solving discrete optimisation problems. In LBBD, the optimisation problem is divided into a master problem and a subproblem and each part is solved separately. LBBD methods that combine mixed-integer programming and constraint programming have been successfully applied to solve large-scale scheduling and resource allocation problems. Such combinations typically solve an assignment-type master problem and a scheduling-type subproblem. However, a challenge with LBBD methods that have feasibility subproblems are that they do not provide a feasible solution until an optimal solution is found.  In this thesis, we show that feasible solutions can be obtained by finding and combining feasible parts of an infeasible master problem assignment. We use these insights to develop an acceleration technique for LBBD that solves a series of subproblems, according to algorithms for constructing a maximal feasible subset of constraints (MaFS). Using a multiprocessor scheduling problem as a benchmark, we study the computational impact from using this technique. We evaluate three variants of LBBD schemes. The first uses MaFS, the second uses irreducible subset of constraints (IIS) and the third combines MaFS with IIS. Computational tests were performed on an instance set of multiprocessor scheduling problems. In total, 83 instances were tested, and their number of tasks varied between 2794 and 10,661. The results showed that when applying our acceleration technique in the decomposition scheme, the pessimistic bounds were strong, but the convergence was slow. The decomposition scheme combining our acceleration technique with the acceleration technique using IIS showed potential to accelerate the method.

This thesis explores the use of a column generation method, a subgradient method, and a logic-based Benders decomposition method on a minimized makespan K-rural postman problem. The K-rural postman problem here describes a search and rescue mission using multiple identical unmanned aerial vehicles (UAVs) to cover an area, represented as a complete graph. Each decomposition method has a separate problem for each UAV. In the subgradient and column generation case, a heuristic is used to find an improved upper bound for the makespan. This upper bound can in turn be used to decrease the feasible regions of the subproblems. Moreover, because the subproblems are slow to solve, a maximum calculation time is used, resulting in a feasible solution and a lower bound for each subproblem. These two modifications to the decomposition methods result in a non-standard behaviour.  Multiple fictional problem instances of different sizes and numbers of UAVs were generated and used for evaluating the methods. A maximal time limit is used in these instances. We conclude that solving the original, non-decomposed, problem for smaller instances with a standard solver is faster and gives better results than the decomposition methods. For larger instances, solving the non-decomposed model led to memory issues on several occasions. However, the suggested subgradient and column generation methods can solve every problem. The logic-based Benders decomposition method performed best on instances with multiple UAVs, but had issues when fewer UAVs are utilized. / Den här masteruppsatsen utforskar användningen av en kolumngenereringsmetod, en subgradientmetod och en logikbaserad Benders dekompositionsmetod på en variant av lantbrevbärarproblemet. Vårat brevbärarprolem beskriver sök- och räddningsuppdrag där $K$ drönare används för att avsöka ett område med målfunktionen att minimera flygtiden för den långsammaste drönaren. Varje dekompositionsmetod använder sig av ett problem för varje drönare. I subgradient- och kolumngenereringsmetoden användes en heuristik för att hitta en bättre övre begränsning till drönarnas flygtid. Den förbättrade övre begränsningen kunde sedan användas för att minska det tillåtna området för de mindre problemen. Eftersom de mindre problem var svårlösta, användes en maximal beräkningstid vilket resulterade i att en tillåten lösning och undre gräns gavs för varje mindre problem. Dessa två modifikationer resulterade i icke typiska beteenden.  Metoderna utvärderades på flera fiktiva testinstanser av olika storlekar där antalet drönare varierar. En tidsbegränsning används på varje probleminstans. Slutsatserna från uppsatsen är de original brevbärare problemet ger bäst lösning och snabbast lösningstid i de mindre instanserna. Vid lösning av större probleminstanser, gav original problemet flerfaldiga gånger minnesproblem. Subgradient- och kolumngenereringsmetoden kunde däremot lösa varje probleminstans inom tidsbegränsningen, vilket gjorde de mer pålitliga. Logikbaserade Benders dekompositionsmetoden presterade bättre i instanser med flera drönare, men stötte på problem i instanser med färre drönare.

In today's competitive environment, the importance of continuous production, quality improvement, and fast delivery has forced production and delivery processes to become highly reliable. Keeping equipment in good condition through maintenance activities can ensure a more reliable system. However, maintenance leads to temporary reduction in capacity that could otherwise be utilized for production. Therefore, the coordination of maintenance and production is important to guarantee good system performance. The central thesis of this dissertation is that integrating maintenance and production decisions increases efficiency by ensuring high quality production, effective resource utilization, and on-time deliveries. Firstly, we study the problem of integrated maintenance and production planning where machines are preventively maintained in the context of a periodic review production system with uncertain yield. Our goal is to provide insight into the optimal maintenance policy, increasing the number of finished products. Specifically, we prove the conditions that guarantee the optimal maintenance policy has a threshold type. Secondly, we address the problem of integrated maintenance planning and production scheduling where machines are correctively maintained in the context of a dynamic aircraft repair shop. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter periods. Our results show that the approach that uses logic-based Benders decomposition to solve the static sub-problems, schedules over longer horizon, and quickly adjusts the schedule increases the utilization of aircraft in the long term. Finally, we tackle the problem of integrated maintenance planning and production scheduling where machines are preventively maintained in the context of a multi-machine production system. Depending on the deterioration process of machines, we design decomposed techniques that deal with the stochastic and combinatorial challenges in different, coupled stages. Our results demonstrate that the integrated approaches decrease the total maintenance and lost production cost, maximizing the on-time deliveries. We also prove sufficient conditions that guarantee the monotonicity of the optimal maintenance policy in both machine state and the number of customer orders. Within these three contexts, this dissertation demonstrates that the integrated maintenance and production decision-making increases the process efficiency to produce high quality products in a timely manner.