Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Fifty years of scheduling: a survey of milestones

Scheduling has become a major field within operational research with several hundred publications appearing each year. This paper explores the historical development of the subject since the mid-1950s when the landmark publications started to appear. A discussion of the main topics of scheduling research for the past five decades is provided, highlighting the key contributions that helped shape the subject. The main topics covered in the respective decades are combinatorial analysis, branch and bound, computational complexity and classification, approximate solution algorithms and enhanced scheduling models.

Batching decisions for assembly production systems

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.

Shop scheduling problems under precedence constraints

The paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, we study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence rela-tions are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.

Optimizing the operation of straight-grate iron-ore pellet induration systems using process models

Mathematical models of straight-grate pellet induration processes have been developed and carefully validated by a number of workers over the past two decades. However, the subsequent exploitation of these models in process optimization is less clear, but obviously requires a sound understanding of how the key factors control the operation. In this article, we show how a thermokinetic model of pellet induration, validated against operating data from one of the Iron Ore Company of Canada (IOCC) lines in Canada, can be exploited in process optimization from the perspective of fuel efficiency, production rate, and product quality. Most existing processes are restricted in the options available for process optimization. Here, we review the role of each of the drying (D), preheating (PH), firing (F), after-firing (AF), and cooling (C) phases of the induration process. We then use the induration process model to evaluate whether the first drying zone is best to use on the up- or down-draft gas-flow stream, and we optimize the on-gas temperature profile in the hood of the PH, F, and AF zones, to reduce the burner fuel by at least 10 pct over the long term. Finally, we consider how efficient and flexible the process could be if some of the structural constraints were removed (i.e., addressed at the design stage). The analysis suggests it should be possible to reduce the burner fuel lead by 35 pct, easily increase production by 5+ pct, and improve pellet quality.

The development and validation of computational MHD techniques for the modelling of metal production processes

Magnetic fields are used in a number of processes related to the extraction of metals, production of alloys and the shaping of metal components. Computational techniques have an increasingly important role to play in the simulation of such processes, since it is often difficult or very costly to conduct experiments in the high temperature conditions encountered and the complex interaction of fluid flow, heat transfer and magnetic fields means simple analytic models are often far removed from reality. In this paper an overview of the computational activity at the University of Greenwich is given in this area, covering the past ten years. The overview is given from the point of view of the modeller and within the space limitations imposed by the format it covers the numerical methods used, attempts at validation against experiments or analytic procedures; it highlights successes, but also some failures. A broad range of models is covered in the review (and accompanying lecture), used to simulate (a) A-C field applications: induction melting, magnetic confinement and levitation, casting and (b) D-C field applications such as: arc welding and aluminium electroloysis. Most of these processes involve phase change of the metal (melting or solidification), the presence of a dynamic free surface and turbulent flow. These issues affect accuracy and need to be address by the modeller.

Decision models - an analytical framework for the Watertime Project

This paper suggests a possible framework for the encapsulation of the decision making process for the Waterime project. The final outcome maybe a computerised model, but the process advocated is not prescriptive, and involves the production of a "paper model" as mediating representation between the knowledge acquired and any computerised system. This paper model may suffice in terms of the project's goals.

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Models for magnetohydrodynamics of aluminium electrolysis cells

The electric current and the associated magnetic field in aluminium electrolysis cells create effects limiting the cell productivity and possibly cause instabilities: surface waving, ‘anode effects’, erosion of pot lining, feed material sedimentation, etc. The instructive analysis is presented via a step by step inclusion of different physical coupling factors affecting the magnetic field, electric current, velocity and wave development in the electrolysis cells. The full time dependent model couples the nonlinear turbulent fluid dynamics and the extended electromagnetic field in the cell, and the whole bus bar circuit with the ferromagnetic effects. Animated examples for the high amperage cells are presented. The theory and numerical model of the electrolysis cell is extended to the cases of variable cell bottom of aluminium layer and the variable thickness of the electrolyte due to the anode non-uniform burn-out process and the presence of the anode channels. The problem of the channel importance is well known Moreau-Evans model) for the stationary interface and the velocity field, and was validated against measurements in commercial cells, particularly with the recently published ‘benchmark’ test for the MHD models of aluminium cells [1]. The presence of electrolyte channels requires also to reconsider the previous magnetohydrodynamic instability theories and the dynamic wave development models. The results indicate the importance of a ‘sloshing’ parametrically excited MHD wave development in the aluminium production cells.

Enhancing the numerical performance of fire field models (CMS Paper)

This paper describes two new techniques designed to enhance the performance of fire field modelling software. The two techniques are "group solvers" and automated dynamic control of the solution process, both of which are currently under development within the SMARTFIRE Computational Fluid Dynamics environment. The "group solver" is a derivation of common solver techniques used to obtain numerical solutions to the algebraic equations associated with fire field modelling. The purpose of "group solvers" is to reduce the computational overheads associated with traditional numerical solvers typically used in fire field modelling applications. In an example, discussed in this paper, the group solver is shown to provide a 37% saving in computational time compared with a traditional solver. The second technique is the automated dynamic control of the solution process, which is achieved through the use of artificial intelligence techniques. This is designed to improve the convergence capabilities of the software while further decreasing the computational overheads. The technique automatically controls solver relaxation using an integrated production rule engine with a blackboard to monitor and implement the required control changes during solution processing. Initial results for a two-dimensional fire simulation are presented that demonstrate the potential for considerable savings in simulation run-times when compared with control sets from various sources. Furthermore, the results demonstrate the potential for enhanced solution reliability due to obtaining acceptable convergence within each time step, unlike some of the comparison simulations.