Multipurpose batch manufacturing systems allow a suite of job types to be processed with a fixed set of machines. These types of systems are commonly found in chemical processing, as well as in computer systems and the service industry. In this thesis we consider the problem of sequencing jobs entering the manufacturing system in order to minimize makespan, or total time to complete processing of the jobs. We formulate this problem as a dynamic programming problem and illustrate the computational difficulty of solving this problem. We give a method for simulation of the system by representing each machine in the system as a finite state automata. This allows one to calculate the makespan given a manufacturing system and a sequence. Due to the complexity of the system, we offer an approximation to the problem. We show that the approximation strategy allows refinement. This progressive refinement of the approximation results in a sequence of approximations that approach the true problem. As the approximation is refined, the computational complexity of the approximated problem grows. For a simplified system, we show that the approximation has bounded error. Furthermore, we show that the error bound of the approximation sequence improves as the approximation approaches the true problem. This presents a trade-off between computational complexity and accuracy of the solution. A decision maker using this sequence of approximations can quickly determine a level of approximation based on the amount of computational power available and the accuracy needed in a solution.

No description available.

This paper presents the development and mathematical implementation of a production scheduling model utilizing mixed-integer linear programming (MILP). A simplified model of a real-world multi-product batch plant constitutes the basis. The paper shows practical extensions to the model, resulting in a digital twin of the plant. Apart from sequential arrangement, the final model contains maintenance periods, campaign planning and storage constraints to a limited extend. To tackle weak computational performance and missing model features, a condensed mathematical formulation is introduced at first. After stating that these measures do not suffice for applicability in a restrained time period, a novel solution strategy is proposed. The overall non-iterative algorithm comprises a multi-step decomposition approach, which starts with a reduced scope and incrementally complements the schedule in multiple subproblem stages. Each of those optimizations holds less decision variables and makes use of warmstart information obtained from the predecessor model. That way, a first feasible solution accelerates the subsequent improvement process. Furthermore, the optimization focus can be shifted beneficially leveraging the Gurobi solver parameters. Findings suggest that correlation may exist between certain characteristics of the scheduling scope and ideal parameter settings, which yield potential for further investigation. Another promising area for future research addresses the concurrent multi-processing of independent MILPs on a single machine. First observations indicate that significant performance gains can be achieved in some cases, though sound dependencies were not discovered yet.

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.