A scatter search for the extended resource renting problem

In this paper, the extended Resource Renting Problem (RRP/extended) is presented. The RRP/extended is a time-constrained project scheduling problem, in which the total project cost is minimised. In the RRP/extended, this total project cost is determined by a number of extra costs, which are defined in this paper. These costs are based on the costs that are used in the traditional Resource Renting Problem and the Total Adjustment Cost Problem. Therefore, the RRP/extended represents a union of these two problems. To solve the RRP/extended, a scatter search is developed. The building blocks of this scatter search are specifically designed for the RRP/extended. We introduce two crossovers and an improvement method. The efficiency of these building blocks will be shown in the paper. Furthermore, a sensitivity analysis is presented in which the five costs have diverse values.     

Maximizing the net present value of a project with linear time-dependent cash flows

The paper studies the unconstrained project-scheduling problem with discounted cash flows where the cash flow functions are assumed to be linear-dependent on the completion times of the corresponding activities. Each activity of this unconstrained project-scheduling problem has a known deterministic cash flow function that is linear and non-increasing in time. Progress payments and cash outflows occur at the completion times of activities. The objective is to schedule the activities in order to maximize the net present value (npv) subject to the precedence constraints and a fixed deadline. Despite the growing amount of research concerning the financial aspects in project scheduling, little research has been done on the problem with time-dependent cash flow functions. Nevertheless, this problem gives an incentive to solve more realistic versions of project-scheduling problems with financial objectives. We introduce an extension of an exact recursive algorithm that has been used in solving the max-npv problem with time-independent cash flow functions and which is embedded in an enumeration procedure. The recursive search algorithm schedules the activities as soon as possible and searches for sets of activities to shift towards the deadline in order to increase the npv. The enumeration procedure enumerates all sets of activities for which such a shift has not been made but could, eventually, have been advantageous. The procedure has been coded in Visual C++ v.4.0 under Windows NT and has been validated on a randomly generated problem set.     

A multi-objective scatter search for the ladle scheduling problem

We consider the ladle scheduling problem, which can be regarded as a vehicle routing problem with semi-soft time windows and adjustment times. The problem concerns allocating ladles to serve molten steel based on a given steelmaking scheduling plan, and determining the modification operations for the empty ladles after the service process. In addition, combining the controllable processing time of molten steel, the other aspect of the problem is to determine the service start times taking into consideration the technological constraints imposed in practice. We present a non-linear mathematical programming model with the conflicting objectives of minimising the occupation ratio of the ladles and maximising the degree of satisfaction with meeting the soft windows. To solve the multi-objective model, we develop a new scatter search (SS) approach by re-designing the common components of SS and incorporating a diversification generator, a combination method and a diversification criterion to conduct a wide exploration of the search space. We analyse and compare the performance of the proposed approach with a multi-objective genetic algorithm and with manual scheduling adopted in practical production using three real-life instances from a well-known iron–steel production plant in China. The computational results demonstrate the effectiveness of the proposed SS approach for solving the ladle scheduling problem.     

An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem

This paper deals with the weighted earliness-tardiness resource-constrained project scheduling problem with minimum and maximum time lags (WET-RCPSP/max). The problem consists of scheduling the activities of a project subject to prescribed resource and temporal constraints such that the total weighted deviation of the activities' completion times from prescribed due dates is minimized. Key applications are planning of just-in-time production and reactive scheduling. For the (approximative) solution of the WET-RCPSP/max, we present a population-based iterated-local-search heuristic. We also report the results of an experimental performance analysis where this heuristic outperformed state-of-the-art methods.     

A multi-objective scatter search for a bi-criteria no-wait flow shop scheduling problem

The flow shop problem as a typical manufacturing challenge has gained wide attention in academic fields. This article considers a bi-criteria no-wait flow shop scheduling problem (FSSP) in which weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a FSSP has been proved to be NP-hard in a strong sense, a new multi-objective scatter search (MOSS) is designed for finding the locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm (GA), i.e. SPEA-II. The computational results show that the proposed MOSS performs better than the above GA, especially for the large-sized problems.     

Simultaneous planning of the project scheduling and material procurement problem under the presence of multiple suppliers

Simultaneous planning of project scheduling and material procurement can improve the project execution costs. Hence, the issue has been addressed here by a mixed-integer programming model. The proposed model facilitates the procurement decisions by accounting for a number of suppliers offering a distinctive discount formula from which to purchase the required materials. It is aimed at developing schedules with the best net present value regarding the obtained benefit and costs of the project execution. A genetic algorithm is applied to deal with the problem, in addition to a modified version equipped with a variable neighbourhood search. The underlying factors of the solution methods are calibrated by the Taguchi method to obtain robust solutions. The performance of the aforementioned methods is compared for different problem sizes, in which the utilized local search proved efficient. Finally, a sensitivity analysis is carried out to check the effect of inflation on the objective function value.     

A search game model of the scatter hoarder's problem

Scatter hoarders are animals (e.g. squirrels) who cache food (nuts) over a number of sites for later collection. A certain minimum amount of food must be recovered, possibly after pilfering by another animal, in order to survive the winter. An optimal caching strategy is one that maximizes the survival probability, given worst case behaviour of the pilferer. We modify certain ‘accumulation games’ studied by Kikuta & Ruckle (2000 J. Optim. Theory Appl.) and Kikuta & Ruckle (2001 Naval Res. Logist.), which modelled the problem of optimal diversification of resources against catastrophic loss, to include the depth at which the food is hidden at each caching site. Optimal caching strategies can then be determined as equilibria in a new ‘caching game’. We show how the distribution of food over sites and the site-depths of the optimal caching varies with the animal''s survival requirements and the amount of pilfering. We show that in some cases, ‘decoy nuts’ are required to be placed above other nuts that are buried further down at the same site. Methods from the field of search games are used. Some empirically observed behaviour can be shown to be optimal in our model.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

A robust scheduling for the multi-mode project scheduling problem with a given deadline under uncertainty of activity duration

The problem of this paper deals with the multi-mode project scheduling problem under uncertainty of activity duration where only the renewable resources are taken into account and a given deadline has to be met at the cost of recruiting additional resources. A heuristic algorithm is employed to solve this problem, and to maintain the robustness of the baseline schedule, the concept of critical chain project management (CCPM) is applied in which a new definition to resource buffer is considered. A simulation methodology is used to determine the size and location of resource buffers in the schedules in which three different buffer sizes and three different uncertainty levels are considered. Results and analysis of the simulation outcomes illustrate that resource buffers are useful and should be simulated by the CCPM schedules, as they help to decrease the total duration of the project during implementation and meet the deadline of the project with more assurance.     

Hybridization of genetic algorithm and fully informed particle swarm for solving the multi-mode resource-constrained project scheduling problem

In this article, the genetic algorithm (GA) and fully informed particle swarm (FIPS) are hybridized for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed hybrid genetic algorithm–fully informed particle swarm algorithm (HGFA), FIPS is a popular variant of the particle swarm optimization algorithm. A random key and the related mode list representation schemes are used as encoding schemes, and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. Furthermore, the existing mode improvement procedure in the literature is modified. The results show that the proposed mode improvement procedure remarkably improves the project makespan. Comparing the results of the proposed HGFA with other approaches using the well-known PSPLIB benchmark sets validates the effectiveness of the proposed algorithm to solve the MRCPSP.     

A heuristic algorithm to minimise the control places of a Petri net for the control of shared machines

This paper proposes a design methodology of a controller based on a Petri net for the shared machines of manufacturing systems. A conflict occurs when several manufacturing systems require the same shared machines at the same time. In this case, we have two issues; the scheduling of jobs on shared machines and the construction of a control procedure for scheduling. The scheduling of production on machines has been extensively studied over the past years by researchers. In this paper, our concern is not the scheduling problem but the construction of a control procedure for the production schedule. We propose a design of a Petri net based controller for the shared machines of manufacturing systems such that the number of control places in the Petri net is minimised. The experimental results show that the proposed algorithm performs better than an upper bound in terms of optimality. Also, the proposed algorithm is computationally more efficient than the optimal algorithm. Finally, we present the application of the proposed algorithm to a realistic batch process system shown in the literature.     

A scatter search approach with dispatching rules for a joint decision of cell formation and parts scheduling in batches

A joint decision of cell formation and parts scheduling is addressed for a cellular manufacturing system where each type of machine and part may have multiple numbers and parts must require processing and transferring in batches. The joint decision problem is not only to assign batches and associated machine groups to cells, but also to sequence the processing of batches on each machine in order to minimise the total tardiness penalty cost. A nonlinear mixed integer programming mathematical model is proposed to formulate the problem. The proposed model, within nonlinear terms and integer variables, is difficult to solve efficiently for real size problems. To solve the model for practical purposes, a scatter search approach with dispatching rules is proposed, which considers two different combination methods and two improvement methods to further expand the conceptual framework and implementation of the scatter search so as to better fit the addressed problem. This scatter search approach interactively uses a combined dispatching rule to solve a scheduling sub-problem corresponding to each integer solution visited in the search process. A computational study is performed on a set of test problems with various dimensions, and computational results demonstrate the effectiveness of the proposed approach.     

Reliability: How much is it worth? Beyond its estimation or prediction, the (net) present value of reliability

In this article, we link an engineering concept, reliability, to a financial and managerial concept, net present value, by exploring the impact of a system's reliability on its revenue generation capability. The framework here developed for non-repairable systems quantitatively captures the value of reliability from a financial standpoint. We show that traditional present value calculations of engineering systems do not account for system reliability, thus over-estimate a system's worth and can therefore lead to flawed investment decisions. It is therefore important to involve reliability engineers upfront before investment decisions are made in technical systems. In addition, the analyses here developed help designers identify the optimal level of reliability that maximizes a system's net present value—the financial value reliability provides to the system minus the cost to achieve this level of reliability. Although we recognize that there are numerous considerations driving the specification of an engineering system's reliability, we contend that the financial analysis of reliability here developed should be made available to decision-makers to support in part, or at least be factored into, the system reliability specification.     

A modified harmony search algorithm for the multi-objective flowshop scheduling problem with due dates

This paper presents a modified harmony search optimisation algorithm (MHSO), specifically designed to solve two- and three-objective permutation flowshop scheduling problems, with due dates. To assess its capability, five sets of scheduling problems have been used to compare the MHSO with a known and highly efficient genetic algorithm (GA) chosen as the benchmark. Obtained results show that the new procedure is successful in exploring large regions of the solution space and in finding a significant number of Pareto non-dominated solutions. For those cases where the exhaustive evaluation of sequences can be applied the algorithm is able to find the whole non-dominated Pareto border, along with a considerable number of solutions that share the same optimal values for the considered optimisation parameters. To validate the algorithm, five sets of scheduling problems are investigated in-depth in comparison with the GA. Results obtained by both methods (exhaustive solutions have been provided as well for small sized problems) are fully described and discussed.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

Beyond its cost, the value of maintenance: An analytical framework for capturing its net present value

Maintenance planning and activities have grown dramatically in importance across many industries and are increasingly recognized as drivers of competitiveness if managed appropriately. Correlated with this observation is the proliferation of maintenance optimization techniques in the technical literature. But while all these models deal with the cost of maintenance (as an objective function or a constraint), only a handful addresses the notion of value of maintenance, and seldom in an analytical or quantitative way.In this paper, we propose that maintenance has intrinsic value and argue that existing cost-centric models ignore an important dimension of maintenance, namely its value, and in so doing, they can lead to sub-optimal maintenance strategies. We develop a framework for capturing and quantifying the value of maintenance activities. Our framework is based on four key components. First, we consider systems that deteriorate stochastically and exhibit multi-state failures, and model their state evolution using Markov chains and directed graphs. Second, we consider that the system provides a flow of service per unit time. This flow in turn is “priced” and a discounted cash flow is calculated resulting in a present value (PV) for each branch of the graph—or “value trajectory” of the system. Third as the system ages or deteriorates, it migrates towards lower PV branches of the graph, or lower value trajectories. Fourth, we conceptualize maintenance as an operator (in a mathematical sense) that raises the system to a higher PV branch in the graph. We refer to the value of maintenance as the incremental PV between the pre- and post-maintenance branches of the graphs minus the cost of maintenance. The framework presented here offers rich possibilities for future work in benchmarking existing maintenance strategies based on their value implications, and in deriving new maintenance strategies that are “value-optimized.”     

Developing a new model for simultaneous scheduling of two grand projects based on game theory and solving the model with Benders decomposition

Grand infrastructure projects, such as dam, power plant, petroleum, and gas industry projects, have several contractors working on them in several independent sub-projects. The concern of reducing the duration of these projects is one of the important issues among various aspects; thus, our aim is to fulfill the requirements by using the game theory approach. In this study, a mixed-integer programming model consisting of game theory and project scheduling is developed to reduce the duration of projects with a minimum increase in costs. In this model, two contractors in successive periods are entered into a step-by-step competition by the employer during dynamic games, considering an exchange in their limited resources. The optimum solution of the game in each stage are selected as the strategy, and the resources during the game are considered to be renewable and limited. The strategy of each contractor can be described as follows: 1) share their resources with the other contractor and 2) not share the resources with the other contractor. This model can act dynamically in all circumstances during project implementation. If a player chooses a non-optimum strategy, then this strategy can immediately update itself at the succeeding time period. The proposed model is solved using the exact Benders decomposition method, which is coded in GAMS software. The results suggest the implementation of four step-by-step games between the contractors. Then, the results of our model are compared with those of the conventional models. The projects’ duration in our model is reduced by 22.2%. The nominal revenue of both contractors has also reached a significant value of 46078 units compared with the relative value of zero units in the original model. Moreover, we observed in both projects the decreases of 19.5%, 20.9%, and 19.7% in the total stagnation of resources of types 1, 2, and 3, respectively.     

A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs

It is shown that the job-shop problem with two machines and a fixed number ofk jobs with makespan criterionJ2¦n=k¦C ^max is polynomially solvable. Sotskov and Shakhlevich (1993) have shown that problemJ3¦n=3¦C _maxisNP-hard. Furthermore it is well known that J¦n=2¦C _maxin polynomially solvable. Thus, our result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.Supported by Deutsche Forschungsgemeinschaft, Project Jop-TAG