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.     

基于本体面向服务的统一制造资源管理

为满足制造企业内不同业务应用系统对制造资源的应用需求,建立面向服务的统一制造资源管理平台是一种有效的解决方式．本文从资源本身的结构及其管理与应用需求两方面出发,参考本体建模的思想,给出了建立面向PDM、CAPP、ERP和MES应用的统一制造资源本体模型的方法,包括资源术语、需求描述的概念化集合、动静态资源数据实体等．在此基础上,采用面向服务的信息技术,构建了一种通用的、可扩展的统一制造资源管理平台．     

Stability and resource allocation in project planning

The majority of resource-constrained project scheduling efforts assume perfect information about the scheduling problem to be solved and a static deterministic environment within which the precomputed baseline schedule is executed. In reality, project activities are subject to considerable uncertainty, which generally leads to numerous schedule disruptions. In this paper, we present a resource allocation model that protects a given baseline schedule against activity duration variability. A branch-and-bound algorithm is developed that solves the proposed resource allocation problem. We report on computational results obtained on a set of benchmark problems.     

A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution

We address a multi-skill project scheduling problem for IT product development in this article. The goal is for product development managers to be able to generate an initial schedule at an early stage of development activities. Due to the complexity of the product structure and functionality, an IT product development effort is divided into multiple projects. Each project includes several tasks, and each task must be completed by an employee who has mastered a certain skill to complete it. A pool of multi-skilled employees is available, and the employees’ skill efficiencies are influenced by both learning and forgetting phenomena. Based on the real-world demands of product development managers, three objectives are simultaneously considered: skill efficiency gain, product development cycle time and costs. To solve this problem, we propose a multi-objective non-linear mixed integer programming model. The Non-dominated Sorting Genetic Algorithm II (NSGA-II)is designed to generate an approximation to the optimal Pareto front of this NP-hard multi-objective optimisation problem. The algorithm produces feasible schedules for all the development projects using the serial schedule generation scheme. We adopt penalty values and individual employee adjustments to address resource conflicts and constraint violations. A weighted ideal point method is used to select the final solution from the approximate Pareto solution set. An application case of a new electrical energy saving product implementation in a leading electrical device company in China is used to illustrate the proposed model and algorithm.     

The resource renting problem subject to temporal constraints

We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported.

---

---

Received: December 1, 1999 / Accepted: November 8, 2000     

A generic resource distribution and test scheduling scheme for embedded core-based SoCs

We present a novel test scheduling algorithm for embedded core-based system-on-chips based on a graph-theoretic formulation. Given a system integrated with a set of cores and a set of test resources, we select a test for each core from a set of alternative test sets, and schedule it in a way to evenly balance the resource usage and to ultimately reduce the test application time. Improvements to the basic algorithm are sought by grouping the cores and assigning higher priorities to those with smaller number of alternate test sets. The algorithm is also extended for solving the general test scheduling problem where multiple test sets are selected for each core from a set of alternatives to facilitate the testing for various fault models. A simulation study is performed to quantify the performance of the proposed scheduling approach.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.     

Underground production scheduling with ventilation and refrigeration considerations

Underground mine production scheduling determines when, if ever, activities associated with the extraction of ore should be executed. The accumulation of heat in the mine where operators are working is a major concern. At the time of this writing, production scheduling and ventilation decisions are not made in concert. Correspondingly, heat limitations are largely ignored. Our mixed-integer program maximizes net present value subject to constraints on precedence, and mill and extraction capacities with the consideration of heat using thermodynamic principles, while affording the option of activating refrigeration to mitigate heat accumulation. In seconds to hours, depending on the problem size (up to thousands of activities and 900 daily time periods), a corresponding methodology that exploits the mathematical problem structure provides schedules that maintain a safe working environment for mine operators; optimality gaps are no more than 15% and average less than half that for otherwise-intractable instances.

     

A ROLLING HORIZON HEURISTIC FOR REACTIVE SCHEDULING OF BATCH PROCESS OPERATIONS

Batch chemical plants are dynamic processing facilities where static production schedules can rarely be adhered to due to market and operating uncertainties. On-line schedule modification of a prior; timing assignments and resource allocations in response to unantipicated disruptions is done through a decomposition heuristic that uses a rolling horizon implementation policy. An attempt is made to minimize the impact of the disruptions on the original schedule near the point of each deviation while exploiting the combinatorial flexibility of task and resource reassignments in future scheduling time windows. The problem is addressed as a multiobjective optimization problem involving completion time criteria, relative customer importance, and production cost considerations.

A rigorous analysis of problem sensitive parameters, including penalty weights and subhorizon length, is conducted. A model plant case study is performed. Variations on storage availability and task flexibility are investigated in an attempt to characterize dominant effects of the weighting parameters. Results indicate that user preference can serve as a strong guide for obtaining near optimal reactive scheduling solutions. It is shown that the combinatories can be controlled and that costly and inefficient full scale rescheduling of multipurpose production facilities can be avoided.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

SCHEDULING A SINGLE MACHINE TO MINIMIZE TWO CRITERIA: MAXIMUM TARDINESS AND NUMBER OF TARDY JOBS

In this paper we consider a single machine scheduling problem with two criteria; minimizing both maximum tardiness and the number of tardy jobs. We present both heuristic and branch-and-bound algorithms to find the schedule which minimizes the number of tardy jobs among all schedules having minimal maximum tardiness. Computational results show that problems with up to 40 jobs can be solved in less than one minute of computer time, and solution difficulty tends to increase as the range of due dates increases relative to the total processing time. We extend our results to generate all nondominated schedules for the two criteria. Computational experiments indicate that all non-dominated solutions to problems with 40 jobs can be generated. However, solution difficulty for these problems is highly dependent on problem parameters.     

Rolling-horizon lot-sizing when set-up times are sequence-dependent

The challenging problem of efficient lot sizing on parallel machines with sequence-dependent set-up times is modelled using a new mixed integer programming (MIP) formulation that permits multiple set-ups per planning period. The resulting model is generally too large to solve optimally and, given that it will be used on a rolling horizon basis with imperfect demand forecasts, approximate models that only generate exact schedules for the immediate periods are developed. Both static and rolling horizon snapshot tests are carried out. The approximate models are tested and found to be practical rolling horizon proxies for the exact model, reducing the dimensionality of the problem and allowing for faster solution by MIP and metaheuristic methods. However, for large problems the approximate models can also consume an impractical amount of computing time and so a rapid solution approach is presented to generate schedules by solving a succession of fast MIP models. Tests show that this approach is able to produce good solutions quickly.     

A new method for workshop real time scheduling

Workshop real time scheduling is one of the key factors in improving manufacturing system efficiency. This is especially true for workshops in which various products are processed simultaneously, and use multipurpose machines. Real time scheduling is appropriate to handle perturbations in the environment of the manufacturing process, a major issue at the shop floor level. The products to be processed have release times and due dates and the resources are multipurpose machines. A decision support system for real time scheduling is described. It is based on an original approach, aiming at searching for characteristics of a set of schedules compatible with the main manufacturing constraints to be satisfied. This set of schedules is obtained by defining sequences of groups of permutable operations for every resource. A method to find such a set is described. We emphasize the use of this group sequence as a decision support system. Significant states and events requiring real time decisions are identified and three main types of decisions are analysed. For each of them, the proposed decision support system is detailed and explained.     

Modelling and scheduling analysis of multi-cluster tools with residency constraints based on time constraint sets

This paper is dedicated to the scheduling problem of multi-cluster tools with process module residency constraints and multiple wafer product types. The problem is formulated as a non-linear programming model based on a set of time constraint sets. An effective algorithm called the time constraint sets based (TCSB) algorithm is presented as a new method to schedule the transport modules to minimise the makespan of a number of wafers. In approach, time constraint sets are maintained for all the resources and necessary operations to exploit the remaining production capacities during the scheduling process. To validate the proposed algorithm on a broader basis, a series of simulation experiments are designed to compare our TCSB algorithm with the benchmark with regard to cluster factor, configuration flexibilities and the variation of the processing times and residency constraint times. The results indicate that the proposed TCSB algorithm gives optimal or near optimal scheduling solutions in most cases.     

Cost optimization for series–parallel execution of a collection of intersecting operation sets

A collection of intersecting sets of operations is considered. These sets of operations are performed successively. The operations of each set are activated simultaneously. Operation durations can be modified. The cost of each operation decreases with the increase in operation duration. In contrast, the additional expenses for each set of operations are proportional to its time. The problem of selecting the durations of all operations that minimize the total cost under constraint on completion time for the whole collection of operation sets is studied. The mathematical model and method to solve this problem are presented. The proposed method is based on a combination of Lagrangian relaxation and dynamic programming. The results of numerical experiments that illustrate the performance of the proposed method are presented. This approach was used for optimization multi-spindle machines and machining lines, but the problem is common in engineering optimization and thus the techniques developed could be useful for other applications.     

A suitable computational strategy for the parametric analysis of problems with multiple contact

The aim of the present work is to develop an application of the LArge Time INcrement (LATIN) approach for the parametric analysis of static problems with multiple contacts. The methodology adopted was originally introduced to solve viscoplastic and large‐transformation problems. Here, the applications concern elastic, quasi‐static structural assemblies with local non‐linearities such as unilateral contact with friction. Our approach is based on a decomposition of the assembly into substructures and interfaces. The interfaces play the vital role of enabling the local non‐linearities, such as contact and friction, to be modelled easily and accurately. The problem on each substructure is solved by the finite element method and an iterative scheme based on the LATIN method is used for the global resolution. More specifically, the objective is to calculate a large number of design configurations. Each design configuration corresponds to a set of values of all the variable parameters (friction coefficients, prestress) which are introduced into the mechanical analysis. A full computation is needed for each set of parameters. Here we propose, as an alternative to carrying out these full computations, to use the capability of the LATIN method to re‐use the solution to a given problem (for one set of parameters) in order to solve similar problems (for the other sets of parameters). Copyright © 2003 John Wiley & Sons, Ltd.     

Capacitated dynamic lotsizing heuristics for serial systems

This paper deals with multi-item capacitated lotsizing in a serial production environment under dynamic demand conditions. The primary objective of this research is to investigate the performance of simple level-by-level heuristics. A problem classification is proposed to distinguish between easy problems and harder ones for which no simple heuristics can be developed. It is shown how simple algorithms can be constructed for the easier problems using a level-by-level approach. These heuristics are the first of their kind for this problem. They are compared with the optimal solution for a set of test problems. The results show that for some problem classes strategies which are frequently used in practice may result in rather poor schedules.     

A new scheduling technique for the resource–constrained project scheduling problem with discounted cash flows

In this paper, we discuss the resource–constrained project scheduling problem with discounted cash flows. We introduce a new schedule construction technique which moves sets of activities to improve the project net present value and consists of two steps. In particular, the inclusion of individual activities into sets, which are then moved together, is crucial in both steps. The first step groups the activities based on the predecessors and successors in the project network, and adds these activities to a set based on their finish time and cash flow. The second step on the contrary does so based on the neighbouring activities in the schedule, which may but need not include precedence related activities. The proposed scheduling method is implemented in a genetic algorithm metaheuristic and we employ a penalty function to improve the algorithm’s feasibility with respect to a tight deadline. All steps of the proposed solution methodology are tested in detail and an extensive computational experiment shows that our results are competitive with existing work.     

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.     

Agent-based project scheduling

Agent technology offers a new way of thinking about many of the classic problems in operations research. Among these are problems such as project scheduling subject to resource constraints. In this paper, we develop and experimentally evaluate eight agent-based algorithms for solving the multimode, resource-constrained project scheduling problem. Our algorithms differ in the priority rules used to control agent access to resources. We apply our approach to a 51-activity project originally published by Maroto and Tormos [1]. We solve the problem using two types of agent-based systems: (i) a system of simple, reactive agents that we call basic agents; and (ii) a system of more complex, deliberative agents that we call enhanced agents. Of the eight priority rules tested, we find that priority based on shortest processing time performs best in terms of schedule quality when applied by basic agents while the priority based on earliest due date performs best when applied by enhanced agents. In comparing agents across priority rules, we find that enhanced agents generate much better schedules (with makespans up to 66% shorter in some cases) and require only slightly more computation time.