Optical Burst Switching (OBS) is an emerging technology for bearing bursty IP traffic directly over Wavelength Division Multiplexing (WDM) links. In OBS network, a key challenge is to reduce the data loss rate with efficient scheduling algorithms. In this work, we first propose a novel traffic aggregation algorithm, namely Tree-based Burst Aggregation (TBA), which aggregates bursts that are routed within a common tree topology into a composite burst and switch them as a single unit whenever possible. Then we propose another set of algorithms are batch scheduling using interval graphs in the core nodes. The algorithms effectively consider the strong correlations among the multiple bursts, and employ the proposed interval graphs and min-cost circular flow techniques to achieve optimized network performance in terms of data loss rate in OBS networks.

Water and energy are very necessary resources for operating any chemical plant and contribute to total costs. Economic reasons notwithstanding, the processing industry has been incentivised to practise sustainable production in which the consumption of energy and water are more efficient, in response to stringent environmental legislation and public perception. Published literature exists for the independent investigation of water and energy optimisation in batch plants. It has been established for the individual problems that, a true optimum can only be obtained if batch production scheduling and water use or energy optimisation are performed simultaneously. However, the simultaneous optimisation of both water and energy within the same production scheduling framework has been largely ignored, due to the potential complexities of such a problem. Additionally, literature addressing the minimisation of water in fixed load problems has usually assumed that the water using operations (washing) are sequence independent. This is unlikely, as equipment units usually perform more than one task in multipurpose batch plants. Since the sequence of tasks in a unit influences both the occurrence and extent of washing in the unit, appropriate consideration of task sequences during production can contribute to wastewater minimisation. This thesis presents a mathematical formulation for the production scheduling of multipurpose batch plants, in which sequence dependent changeover costs are addressed. When compared to an existing formulation, the proposed formulation leads to a smaller sized model with fewer binary variables, continuous variables and constraints for a given case study, although the same objective was obtained. Expanding upon this, a mathematical formulation for simultaneous batch production scheduling and wastewater minimisation, for which the water requirement in a unit is dependent on tasks and their successors, is presented. The effectiveness of the formulation was demonstrated using two case studies. The results show improvements in profit and reduced wastewater generation when the sequence of tasks is taken into consideration. One case study saw water savings of 48% achieved with this method. The formulation was extended to incorporate process integration in the form of direct water reuse, which resulted in a further improvement in profit and water use. The third contribution in this thesis is a simultaneous method for the optimisation of energy and water embedded within a scheduling framework. In addition, opportunities for direct and indirect heat integration as well as direct and indirect water reuse were explored with the objective of improving the profitability of the plant while minimising water and external utility usage. The applicability of the method was demonstrated with three case studies. The developed formulation proved superior to a method that solved the same problem sequentially. / Thesis (PhD)--University of Pretoria, 2017. / Chemical Engineering / PhD / Unrestricted

<p> Supply chain management is a major issue in many industries as firms realize the importance of creating an integrated relationship with their suppliers and customers. In many manufacturing organizations minimizing the total cost of inventory holding and delivery plays a major role in production scheduling. Inventory holding cost is proportional to the flow time of jobs at the shop. Therefore, we study single machine batch scheduling problems to minimize the sum of weighted flow time and the delivery cost in supply chains.</p> <p> It has been proven that many single machine batch scheduling problems even at the supplier level and the manufacturer level are hard problems to be solved. Therefore, batch scheduling problems for supplier-manufacturer coordination are even harder. Hence, heuristic algorithms may be developed to solve such problems. A good heuristic can be developed only when the specific properties of the given problem are analyzed thoroughly. Since there are many problems at the supplier level and manufacturer level not yet solved, we study single machine scheduling problems under different conditions at the supplier and manufacturer. Then we study batch scheduling problems in a supplier-manufacturer system.</p> <p> We first study some polynomially solvable problems at the supplier and at the manufacturer. Batch scheduling problems at the supplier when jobs have arbitrary processing times and arbitrary weights are intractable. We provide a 2-approximation algorithm for this problem. The performance of this 2-approximation algorithm shows that it provides close to optimal solutions for practical situations. Batch scheduling problems at the manufacturer of multi-product case is intractable even if the weights are identical. We provide a 2-approximation algorithm for this problem and a hybrid meta-heuristic algorithm for the arbitrary weight case. We develop an algorithm for the lower bound of this problem and compare the result of the heuristic algorithm with that of the lower bound solution.</p> <p> Then some batch scheduling problems at the manufacturer in a customer centric supply chain are analysed and dynamic programming algorithms are developed to solve these problems optimally. Finally batch scheduling with supplier manufacturer coordination is studied and there again dynamic programming algorithms are developed to solve the batch scheduling problems of given job sequence under two different conditions.</p> / Thesis / Doctor of Philosophy (PhD)

In this study, a single machine batch-scheduling problem with incompatible jobs and dynamic arrivals is examined. The objective function is the minimization of the total flow time of the jobs. For solving problems a case specific branch and bound algorithm with a heuristic upper bound scheme and two alternative lower bound procedures is used. An extensive computational experiment is conducted to investigate the effects of certain parameters on the computation time. For the most difficult parameter combination branch and bound algorithm can solve the problems about 25 jobs with 4 different job types in a 10 minutes time on average. For the problem types with higher number of jobs and the most difficult parameter combination proposed upper bound heuristic can be used to obtain near optimal solutions.

abstract: This research is motivated by a deterministic scheduling problem that is fairly common in manufacturing environments, where there are certain processes that call for a machine working on multiple jobs at the same time. An example of such an environment is wafer fabrication in the semiconductor industry where some stages can be modeled as batch processes. There has been significant work done in the past in the field of a single stage of parallel machines which process jobs in batches. The primary motivation behind this research is to extend the research done in this area to a two-stage flow-shop where jobs arrive with unequal ready times and belong to incompatible job families with the goal of minimizing total weighted tardiness. As a first step to propose solutions, a mixed integer mathematical model is developed which tackles the problem at hand. The problem is NP-hard and thus the developed mathematical program can only solve problem instances of smaller sizes in a reasonable amount of time. The next step is to build heuristics which can provide feasible solutions in polynomial time for larger problem instances. The basic nature of the heuristics proposed is time window decomposition, where jobs within a moving time frame are considered for batching each time a machine becomes available on either stage. The Apparent Tardiness Cost (ATC) rule is used to build batches, and is modified to calculate ATC indices on a batch as well as a job level. An improvisation to the above heuristic is proposed, where the heuristic is run iteratively, each time assigning start times of jobs on the second stage as due dates for the jobs on the first stage. The underlying logic behind the iterative approach is to improve the way due dates are estimated for the first stage based on assigned due dates for jobs in the second stage. An important study carried out as part of this research is to analyze the bottleneck stage in terms of its location and how it affects the performance measure. Extensive experimentation is carried out to test how the quality of the solution varies when input parameters are varied between high and low values. / Dissertation/Thesis / M.S. Industrial Engineering 2012

Despite recent advances in computer power and the development of better algorithms, theoretical scheduling methodologies developed for batch-chemical production are seldom applied in industry (Musier & Evans 1989 and Grossmann et al. 1992). Scheduling decisions may have significant impact on overall company profitability by defining how capital is utilized, the operating costs required, and the ability to meet due dates. The purpose of this research is to compare different production scheduling methods by applying them to a real-world multi-stage, multi-product, batch-chemical production line. This research addresses the problem that the theoretical algorithms are seldom applied in industry and allows for performance analysis of several theoretical algorithms. The research presented in this thesis focuses on the development and comparison of several scheduling algorithms. The two objectives of this research are to: 1. modify different heuristic production scheduling algorithms to minimize tardiness for a multi-product batch plant involving multiple processing stages with several out-of-phase parallel machines in each stage; and 2. compare the robustness and performance of these production schedules using a stochastic discrete event simulation of a real-world production line. The following three scheduling algorithms are compared: 1. a modified Musier and Evans scheduling algorithm (1989); 2. a modified Ku and Karimi Sequence Building Algorithm (1991); and 3. a greedy heuristic based on an earliest-due-date (EDD) policy. Musier and Evans' heuristic improvement method (1989) is applied to the three algorithms. The computation times to determine the total tardiness of each schedule are compared. Finally, all the schedules are tested for robustness and performance in a stochastic setting with the use of a discrete event simulation (DES) model. Mignon, Honkomp, and Reklaitis' evaluation techniques (1995) and Multiple Comparison of the Best are used to help determine the best algorithm. / Master of Science

Scheduling concerns the allocation of limited resources to tasks over time. In manufacturing systems, scheduling is nothing but assigning the jobs to the available processors over a period of time. Our research focuses on scheduling in systems of parallel processors which is challenging both from the theoretical and practical perspectives. The system of parallel processors is a common occurrence in different types of modern manufacturing systems such as job shop, batch shop and mass production. A variety of important and challenging problems with realistic settings in a system of parallel processors are considered. We consider two types of processors comprising discrete and batch processors. The processor which produces one job at a time is called a discrete processor. Batch processor is a processor that can produce several jobs simultaneously by keeping jobs in a batch form which is commonly seen in semiconductor manufacturing, heat treatment operations and also in chemical processing industries. Our aim is to develop efficient solution methodologies (heuristics/metaheuristics) for three different problems in the thesis. The first two problems consider the objective of minimizing total weighted tardiness in cases of discrete and batch processors where customer delivery time performance is critical. The third problem deals with the objective of minimizing the total weighted completion time in the case of batch processors to reduce work-in-process inventory. Specifically, the first problem deals with the scheduling of parallel identical discrete processors to minimize total weighted tardiness. We develop a metaheuristic based on Ant Colony Optimization(ACO) approach to solve the problem and compare it with the available best heuristics in the literature such as apparent tardiness cost and modified due date rules. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with varied tardiness factors. Our experimentation shows that the proposed ant conony optimization algorithm yields promising results as compared to the best of the available heuristics. The second problem concerns with the scheduling of jobs to parallel identical batch processors for minimizing the total weighted tardiness. It is assumed that the jobs are incompatible in respect of job families indicating that jobs from different families cannot be processed together. We decompose the problem into two stages including batch formation and batch scheduling as in the literature. Ant colony optimization based heuristics are developed in which ACO is used to solve the batch scheduling problem. Our computational experimentation shows that the proposed five ACO based heuristics perform better than the available best traditional dispatching rule called ATC-BATC rule. The third scheduling problem is to minimize the total weighted completion time in a system of parallel identical batch processors. In the real world manufacturing system, jobs to be scheduled come in lots with different job volumes(i.e number of jobs) and priorities. The real settings of lots and high batch capacity are considered in this problem. This scheduling problem is formulated as a mixed integer non-linear program. We develop a solution framework based on the decomposition approach for this problem. Two heuristics are proposed based on the proposed decomposition approach and the performance of these heuristics is evaluated in the cases of two and three batch processors by comparing with the solution of LINGO solver.

Um Erkenntnisse aus großen Mengen wissenschaftlicher Rohdaten zu gewinnen, sind komplexe Datenanalysen erforderlich. Scientific Workflows sind ein Ansatz zur Umsetzung solcher Datenanalysen. Um Skalierbarkeit zu erreichen, setzen die meisten Workflow-Management-Systeme auf bereits existierende Lösungen zur Verwaltung verteilter Ressourcen, etwa Batch-Scheduling-Systeme. Die Abschätzung der Ressourcen, die zur Ausführung einzelner Arbeitsschritte benötigt werden, wird dabei immer noch an die Nutzer:innen delegiert. Dies schränkt die Leistung und Benutzerfreundlichkeit von Workflow-Management-Systemen ein, da den Nutzer:innen oft die Zeit, das Fachwissen oder die Anreize fehlen, den Ressourcenverbrauch genau abzuschätzen. Diese Arbeit untersucht, wie die Ressourcennutzung während der Ausführung von Workflows automatisch erlernt werden kann. Im Gegensatz zu früheren Arbeiten werden Scheduling und Vorhersage von Ressourcenverbrauch in einem engeren Zusammenhang betrachtet. Dies bringt verschiedene Herausforderungen mit sich, wie die Quantifizierung der Auswirkungen von Vorhersagefehlern auf die Systemleistung. Die wichtigsten Beiträge dieser Arbeit sind: 1. Eine Literaturübersicht aktueller Ansätze zur Vorhersage von Spitzenspeicherverbrauch mittels maschinellen Lernens im Kontext von Batch-Scheduling-Systemen. 2. Ein Scheduling-Verfahren, das statistische Methoden verwendet, um vorherzusagen, welche Scheduling-Entscheidungen verbessert werden können. 3. Ein Ansatz zur Nutzung von zur Laufzeit gemessenem Spitzenspeicherverbrauch in Vorhersagemodellen, die die fortwährende Optimierung der Ressourcenallokation erlauben. Umfangreiche Simulationsexperimente geben Einblicke in Schlüsseleigenschaften von Scheduling-Heuristiken und Vorhersagemodellen. 4. Ein Vorhersagemodell, das die asymmetrischen Kosten überschätzten und unterschätzten Speicherverbrauchs berücksichtigt, sowie die Folgekosten von Vorhersagefehlern einbezieht. / Scientific experiments produce data at unprecedented volumes and resolutions. For the extraction of insights from large sets of raw data, complex analysis workflows are necessary. Scientific workflows enable such data analyses at scale. To achieve scalability, most workflow management systems are designed as an additional layer on top of distributed resource managers, such as batch schedulers or distributed data processing frameworks. However, like distributed resource managers, they do not automatically determine the amount of resources required for executing individual tasks in a workflow. The status quo is that workflow management systems delegate the challenge of estimating resource usage to the user. This limits the performance and ease-of-use of scientific workflow management systems, as users often lack the time, expertise, or incentives to estimate resource usage accurately. This thesis is an investigation of how to learn and predict resource usage during workflow execution. In contrast to prior work, an integrated perspective on prediction and scheduling is taken, which introduces various challenges, such as quantifying the effects of prediction errors on system performance. The main contributions are: 1. A survey of peak memory usage prediction in batch processing environments. It provides an overview of prior machine learning approaches, commonly used features, evaluation metrics, and data sets. 2. A static workflow scheduling method that uses statistical methods to predict which scheduling decisions can be improved. 3. A feedback-based approach to scheduling and predictive resource allocation, which is extensively evaluated using simulation. The results provide insights into the desirable characteristics of scheduling heuristics and prediction models. 4. A prediction model that reduces memory wastage. The design takes into account the asymmetric costs of overestimation and underestimation, as well as follow up costs of prediction errors.

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.