A new heuristic for three-machine flow shop scheduling

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.

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.

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.

SMARTFIRE: an intelligent CFD-based fire model

This paper describes a project aimed at making Computational Fluid Dynamics (CFD) based fire simulation accessible to members of the fire safety engineering community. Over the past few years, the practise of CFD based fire simulation has begun the transition from the confines of the research laboratory to the desk of the fire safety engineer. To a certain extent, this move has been driven by the demands of performance based building codes. However, while CFD modelling has many benefits over other forms of fire simulation, it requires a great deal of expertise on the user’s part to obtain reasonable simulation results. The project described in this paper, SMARTFIRE, aims to relieve some of this dependence on expertise so that users are less concerned with the details of CFD analysis and can concentrate on results. This aim is achieved by the use of an expert system component as part of the software suite which takes some of the expertise burden away from the user. SMARTFIRE also makes use of the latest developments in CFD technology in order to make the CFD analysis more efficient. This paper describes design considerations of the SMARTFIRE software, emphasising its open architecture, CFD engine and knowledge based systems.

The FUELCON meta-architecture, in the landscape of intelligent technologies for refuelling

The conception of the FUELCON architecture, of a composite tool for the generation and validation of patterns for assigning fuel assemblies to the positions in the grid of a reactor core section, has undergone an evolution throughout the history of the project. Different options for various subtask were possible, envisioned, or actually explored or adopted. We project these successive, or even concomitant configurations of the architecture, into a meta-architecture, which quite not by chance happens to reflect basic choices in the field's history over the last decade.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Intelligent technologies for nuclear power systems: heuristic and neural tools

The consecutive, partly overlapping emergence of expert systems and then neural computation methods among intelligent technologies, is reflected in the evolving scene of their application to nuclear engineering. This paper provides a bird's eye view of the state of the application in the domain, along with a review of a particular task, the one perhaps economically more important: refueling design in nuclear power reactors.

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Heuristics for short route job shop scheduling problems

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

A heuristic algorithm for two-machine re-entrant shop scheduling

This paper considers the problem of sequencing n jobs in a two‐machine re‐entrant shopwith the objective of minimizing the maximum completion time. The shop consists of twomachines, M1 and M2 , and each job has the processing route (M1 , M2 , M1 ). An O(n log n)time heuristic is presented which generates a schedule with length at most 4/3 times that ofan optimal schedule, thereby improving the best previously available worst‐case performanceratio of 3/2.

SMARTFIRE: an intelligent CFD based fire model

This paper describes a project aimed at making Computational Fluid Dynamics (CFD)- based fire simulation accessible to members of the fire safety engineering community. Over the past few years, the practice of CFD-based fire simulation has begun the transition from the confines of the research laboratory to the desk of the fire safety engineer. To a certain extent, this move has been driven by the demands of performance based building codes. However, while CFD modeling has many benefits over other forms of fire simulation, it requires a great deal of expertise on the user’s part to obtain reasonable simulation results. The project described in this paper, SMARTFIRE, aims to relieve some of this dependence on expertise so that users are less concerned with the details of CFD analysis and can concentrate on results. This aim is achieved by the use of an expert system component as part of the software suite which takes some of the expertise burden away from the user. SMARTFIRE also makes use of the latest developments in CFD technology in order to make the CFD analysis more efficient. This paper describes design considerations of the SMARTFIRE software, emphasizing its open architecture, CFD engine and knowledge-based systems.

An intelligent assistant for design and material engineers in the submarine cable industry

This paper describes an industrial application of case-based reasoning in engineering. The application involves an integration of case-based reasoning (CBR) retrieval techniques with a relational database. The database is specially designed as a repository of experiential knowledge and with the CBR application in mind such as to include qualitative search indices. The application is for an intelligent assistant for design and material engineers in the submarine cable industry. The system consists of three components; a material classifier and a database of experiential knowledge and a CBR system is used to retrieve similar past cases based on component descriptions. Work has shown that an uncommon retrieval technique, hierarchical searching, well represents several search indices and that this techniques aids the implementation of advanced techniques such as context sensitive weights. The system is currently undergoing user testing at the Alcatel Submarine Cables site in Greenwich. Plans are for wider testing and deployment over several sites internationally.

The integration of an intelligent knowledge-based system into engineering software using the blackboard structure

Over recent years there has been an increase in the use of generic Computational Fluid Dynamics (CFD) software packages spread across various application fields. This has created the need for the integration of expertise into CFD software. Expertise can be integrated into CFD software in the form of an Intelligent Knowledge-Based System (IKBS). The advantages of integrating intelligence into generic engineering software are discussed with a special view to software engineering considerations. The software modelling cycle of a typical engineering problem is identified and the respective expertise and user control needed for each modelling phase is shown. The requirements of an IKBS for CFD software are discussed and compared to current practice. The blackboard software architecture is presented. This is shown to be appropriate for the integration of an IKBS into an engineering software package. This is demonstrated through the presentation of the prototype CFD software package FLOWES.