Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data

We consider a total flow time minimisation problem of uniform parallel machine scheduling when job processing times are only known to be bounded within certain given intervals. A minmax regret model is proposed to identify a robust schedule that minimises the maximum deviation from the optimal total flow time over all possible realisations of the job processing times. To solve this problem, we first prove that the maximal regret for any schedule can be obtained in polynomial time. Then, we derive a mixed-integer linear programming (MILP) formulation of our problem by exploiting its structural properties. To reduce the computational time, we further transform our problem into a robust single-machine scheduling problem and derive another MILP formulation with fewer variables and constraints. Moreover, we prove that the optimal schedule under the midpoint scenario is a 2-approximation for our minmax regret problem. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

A branch-and-bound algorithm for the cell formation problem

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.     

A modified entropy-based dynamic gravity model for the evacuation trip distribution problem during typhoons

Typhoon Morakot, which formed on 2 August 2009, was the deadliest typhoon in Taiwan’s history, responsible for over 700 deaths on the island. During the typhoon evacuation process, one critical issue is how to efficiently distribute the evacuation trips to a limited number of shelters based on both spatial and temporal considerations. This paper proposes a modified entropy-based dynamic gravity model to reflect the spatial and temporal distribution of the evacuees and the shelters. A unique feature of the proposed model is that the entropy is explicitly incorporated within the travel cost constraints. The spatial and temporal relationships between evacuees and shelters can be reflected through the impedance functions and the discretized time intervals with better performance than the traditional model. A simulation-assignment model is applied to generate the zone-to-zone travel time. A calibration analysis based on the solution procedure is conducted for the Jiasian network, in Kaohsiung city, which was heavily affected by the Typhoon Morakot. The calibration results show that the modified entropy-based dynamic gravity model leads to better convergence patterns in the entropy values, higher travel cost coefficients, and lower average generalized trip costs than the traditional model, and is suitable for use with the evacuation plan during typhoons.     

Comparison of robust,reliability-based and non-probabilistic topology optimization under uncertain loads and stress constraints

It is nowadays widely acknowledged that optimal structural design should be robust with respect to the uncertainties in loads and material parameters. However, there are several alternatives to consider such uncertainties in structural optimization problems. This paper presents a comprehensive comparison between the results of three different approaches to topology optimization under uncertain loading, considering stress constraints: (1) the robust formulation, which requires only the mean and standard deviation of stresses at each element; (2) the reliability-based formulation, which imposes a reliability constraint on computed stresses; (3) the non-probabilistic formulation, which considers a worst-case scenario for the stresses caused by uncertain loads. The information required by each method, regarding the uncertain loads, and the uncertainty propagation approach used in each case is quite different. The robust formulation requires only mean and standard deviation of uncertain loads; stresses are computed via a first-order perturbation approach. The reliability-based formulation requires full probability distributions of random loads, reliability constraints are computed via a first-order performance measure approach. The non-probabilistic formulation is applicable for bounded uncertain loads; only lower and upper bounds are used, and worst-case stresses are computed via a nested optimization with anti-optimization. The three approaches are quite different in the handling of uncertainties; however, the basic topology optimization framework is the same: the traditional density approach is employed for material parameterization, while the augmented Lagrangian method is employed to solve the resulting problem, in order to handle the large number of stress constraints. Results are computed for two reference problems: similarities and differences between optimized topologies obtained with the three formulations are exploited and discussed.     

Evacuation strategies for vertical ship lift during initial fire: Integrated application of stairs and elevators

Vertical ship lifts (VSLs) are widely used in navigation facilities worldwide because of their efficiency and low cost. Although several researchers have investigated fire evacuation strategies for reducing potential safety hazards in VSLs, an effective and integrated application of stairs and elevators when a fire occurs in a VSL is necessary. Several evacuation routes were analyzed according to VSL structure and evacuation times in this study. Objective function corresponding to the minimum vertical evacuation time and related simulation model was subsequently developed to obtain a cooperative evacuation plan considering different numbers of evacuees. The Three Gorges ship lift was used as an example, and simulation results indicate that number of evacuees and exit selection are the main influencing factors of the total evacuation time in the stair- and elevator-coordinated evacuation mode. Furthermore, the distance between people trapped in ship reception chamber and evacuation exits affects evacuees’ choice of exits. The proposed model can provide a theoretical reference for evacuation research during initial fire events in VSLs.     

Bad-scenario-set robust scheduling for a job shop to hedge against processing time uncertainty

This paper proposed two robust scheduling formulations in real manufacturing systems based on the concept of bad scenario set to hedge against processing time uncertainty, which is described by discrete scenarios. Two proposed robust scheduling formulations are applied to an uncertain job-shop scheduling problem with the makespan as the performance criterion. The united-scenario neighbourhood (UN) structure is constructed based on bad scenario set for the scenario job-shop scheduling problem. A tabu search (TS) algorithm with the UN structure is developed to solve the proposed robust scheduling problem. An extensive experiment was conducted. The computational results show that the first robust scheduling formulation could be preferred to the second one for the discussed problem. It is also verified that the obtained robust solutions could hedge against the processing time uncertainty through decreasing the number of bad scenarios and the degree of performance degradation on bad scenarios. Moreover, the computational results demonstrate that the developed TS algorithm is competitive for the proposed robust scheduling formulations.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

Inventory-based dispatching of automated guided vehicles on container terminals

This paper deals with automated guided vehicles (AGVs) which transport containers between the quay and the stack on automated container terminals. The focus is on the assignment of transportation jobs to AGVs within a terminal control system operating in real time. First, we describe a rather common problem formulation based on due times for the jobs and solve this problem both with a greedy priority rule based heuristic and with an exact algorithm. Subsequently, we present an alternative formulation of the assignment problem, which does not include due times. This formulation is based on a rough analogy to inventory management and is solved using an exact algorithm. The idea behind this alternative formulation is to avoid estimates of driving times, completion times, due times, and tardiness because such estimates are often highly unreliable in practice and do not allow for accurate planning. By means of simulation, we then analyze the different approaches. We show that the inventory-based model leads to better productivity on the terminal than the due-time-based formulation.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

Productivity improvement through a sequencing generalised assignment in an assembly line system

This paper considers the assignment of heterogeneous workers to workstations of an assembly line in order to minimise the total production time. As the structure of the system implies that each of the workstations needs at least one worker, thus the problem can be considered as a generalised assignment problem (GAP). The objective is to perform an efficient human resource planning for a specified horizon consisting of several periods. Hence, we present an extension of the generalised assignment problem, consisting of a set of GAPs (one for each planning period) in which each GAP depends on the previous ones. A mixed integer mathematical model is presented for this sequencing assignment problem. The model is solved by an exact algorithm using Gurobi solver. It is proved that the problem is NP-hard and solving the medium and large size instances is not possible by the exact algorithms. Hence, two matheuristic approaches based on the disaggregated formulation of GAP are proposed. The first approach solves the problem through two sub-problems as the transportation formulation and assignment formulation. The second approach solves the problem by decomposition of the problem into several classical GAPs. The approaches are examined by a total of 27 instances. The results illustrate the efficiency of the proposed algorithms in the computational time and accuracy of the solutions.     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

Staffing a call center with uncertain non-stationary arrival rate and flexibility

We consider a multi-period staffing problem in a single-shift call center. The call center handles inbound calls, as well as some alternative back-office jobs. The call arrival process is assumed to follow a doubly non-stationary stochastic process with a random mean arrival rate. The inbound calls have to be handled as quickly as possible, while the back-office jobs, such as answering emails, may be delayed to some extent. The staffing problem is modeled as a generalized newsboy-type model under an expected cost criterion. Two different solution approaches are considered. First, by discretization of the underlying probability distribution, we explicitly formulate the expected cost newsboy-type formulation as a stochastic program. Second, we develop a robust programming formulation. The characteristics of the two methods and the associated optimal solutions are illustrated through a numerical study based on real-life data. In particular we focus on the numerical tractability of each formulation. We also show that the alternative workload of back-office jobs offers an interesting flexibility allowing to decrease the total operating cost of the call center.     

Modeling emergency evacuation for major hazard industrial sites

A model providing the temporal and spatial distribution of the population under evacuation around a major hazard facility is developed. A discrete state stochastic Markov process simulates the movement of the evacuees. The area around the hazardous facility is divided into nodes connected among themselves with links representing the road system of the area. Transition from node-to-node is simulated as a random process where the probability of transition depends on the dynamically changed states of the destination and origin nodes and on the link between them. Solution of the Markov process provides the expected distribution of the evacuees in the nodes of the area as a function of time. A Monte Carlo solution of the model provides in addition a sample of actual trajectories of the evacuees. This information coupled with an accident analysis which provides the spatial and temporal distribution of the extreme phenomenon following an accident, determines a sample of the actual doses received by the evacuees. Both the average dose and the actual distribution of doses are then used as measures in evaluating alternative emergency response strategies. It is shown that in some cases the estimation of the health consequences by the average dose might be either too conservative or too non-conservative relative to the one corresponding to the distribution of the received dose and hence not a suitable measure to evaluate alternative evacuation strategies.     

High-order nodal discontinuous Galerkin methods for the Maxwell eigenvalue problem

The Maxwell eigenvalue problem is known to pose difficulties for standard numerical methods, predominantly due to its large null space. As an alternative to the widespread use of Galerkin finite-element methods based on curl-conforming elements, we propose to use high-order nodal elements in a discontinuous element scheme. We consider both two- and three-dimensional problems and show the former to be without problems in a wide range of cases. Numerical experiments suggest the validity of this for general problems. For the three-dimensional eigenproblem, we encounter difficulties with a naive formulation of the scheme and propose minor modifications, intimately related to the discontinuous nature of the formulation, to overcome these concerns. We conclude by connecting the findings to time domain solution of Maxwell's equations. The discussion, analysis, and numerous computational experiments suggest that using discontinuous element schemes for solving Maxwell's equation in the frequency- or time-domain present a high-order accurate, efficient and robust alternative to classical Galerkin finite-element methods.     

Accuracy and efficiency of higher-order boundary element methods for steady convective heat diffusion in three-dimensions

Higher-order boundary element methods (BEM) are presented for three-dimenisonal steady convective heat diffusion at high Peclet numbers. The boundary element formulation is facilitated by the definition of an influence domain due to convective kernels. This approach essentially localizes the surface integrations only within the domain of influence which becomes more narrowly focused as the Peclet number increases. The outcome of this phenomenon is an increased sparsity and improved conditioning of the global matrix. Therefore, iterative solvers for sparse matrices become a very efficient and robust tool for the corresponding boundary element matrices. In this paper, we consider an example problem with an exact solution and investigate the accuracy and efficiency of the higher-order BEM formulations for high Peclet numbers in the range from 1000 to 100,000. The bi-quartic boundary elements included in this study are shown to provide very efficient and extremely accurate solutions to this problem, even on a single engineering workstation.     

Godunov Method for Stefan Problems with Enthalpy Formulations

A Stefan problem is a free boundary problem where a phase boundary moves as a function of time. In this article, we consider one-dimensional and two-dimensional enthalpy-formulated Stefan problems. The enthalpy formulation has the advantage that the governing equations stay the same, regardless of the material state (liquid or solid). Numerical solutions are obtained by implementing the Godunov method. Our simulation of the temperature distribution and interface position for the one-dimensional Stefan problem is validated against the exact solution, and the method is then applied to the two-dimensional Stefan problem with reference to cryosurgery, where extremely cold temperatures are applied to destroy cancer cells. The temperature distribution and interface position obtained provide important information to control the cryosurgery procedure.     

Local search for nonpreemptive multi-mode resource-constrained project scheduling

This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewable resources. We provide a well known 0-1 problem formulation and stress the importance of the model by giving applications within production and operations management. Furthermore, we prove that the feasibility problem is already NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to optimality; heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search method that first tries to find a feasible solution and secondly performs a single-neighborhood search on the set of feasible mode assignments. To evaluate the new procedure we perform a rigorous computational study on two benchmark sets. The experiment includes a comparison of our procedure with other heuristics.     

Matheuristic approaches for Q-coverage problem versions in wireless sensor networks

This article deals with sensor coverage scheduling in wireless sensor networks subject to Q-coverage constraints. The main concern is to maximize the network lifetime, while ensuring that each target is covered by a given number of sensors. Three different variations of this problem are considered. Column generation based exact approaches are developed for those problems where the auxiliary problem is solved by a two-level approach comprising a genetic algorithm and an integer linear programming formulation. The genetic algorithm takes advantage of the auxiliary problem structure and appears to be very efficient at providing the master problem with attractive columns. The auxiliary problem integer linear programming (ILP) formulation is then mostly used for proving the optimality status of the current master problem solution. The proposed approaches are shown to be significantly faster than column generation approaches relying only on the auxiliary problem ILP formulation.     

Location and allocation of service units on a congested network

We consider the problem of locating facilities and allocating servers on a congested network (LASCN). Demands for service that originate from the nodes are assumed to be Poisson distributed and the servers provide a service time that is exponentially distributed. The objective is to minimize the total cost of the system which includes a fixed installation cost, a variable server cost, a cost associated with travel time and a cost associated with the waiting time in the facility for all the customers. The problem is formulated using non-linear programming and subsequently analyzed. Results for exact and approximate solution approaches are reported. We also show that we can modify the approaches to solve the LASCN with constraints limiting both the travel time to the servers and the waiting time of customers.     

Minimum norm solutions to linear elastic analysis problems

A basic problem in the linear elastic analysis is that of finding the vectors of stresses and strains, given a finite element model of a structure and a set of external loads. One purpose of this paper is to show that the problem is a special case of the minimum norm problem for underdetermined systems of linear equations. In this regard, the three conventional structural analysis approaches, i.e. the displacement method, the natural factor formulation and the force method, are unified and interpreted in the framework of the minimum norm problem, which is divided into two approaches—the primal formulation and the dual formulation. Numerical comparisons of several computational procedures capable of solving the minimum norm problem are given from computational efficiency and accuracy points of view. Included in the comparisons are the three conventional structural analysis approaches mentioned above, and several alternative approaches.