Multi-mode resource constrained multi-project scheduling and resource portfolio problem

This paper introduces a multi-project problem environment which involves multiple projects with assigned due dates; activities that have alternative resource usage modes; a resource dedication policy that does not allow sharing of resources among projects throughout the planning horizon; and a total budget. Three issues arise when investigating this multi-project environment. First, the total budget should be distributed among different resource types to determine the general resource capacities, which correspond to the total amount for each renewable resource to be dedicated to the projects. With the general resource capacities at hand, the next issue is to determine the amounts of resources to be dedicated to the individual projects. The dedication of resources reduces the scheduling of the projects’ activities to a multi-mode resource constrained project scheduling problem (MRCPSP) for each individual project. Finally, the last issue is the efficient solution of the resulting MRCPSPs. In this paper, this multi-project environment is modeled in an integrated fashion and designated as the resource portfolio problem. A two-phase and a monolithic genetic algorithm are proposed as two solution approaches, each of which employs a new improvement move designated as the combinatorial auction for resource portfolio and the combinatorial auction for resource dedication. A computational study using test problems demonstrated the effectiveness of the solution approach proposed.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Scheduling unit-time tasks in renewable resource constrained flowshops

In this paper we address the problem of scheduling unit time jobs in a flowshop to minimize makespan under a discrete renewable resource constraint. We propose algorithms having complexityO(n) for special cases of two machine and three machine problems. For the three machineN P-hard problem we develop a branch and bound procedure and several upper and lower bounds. We test the efficiency of the procedure and report our computational experience.Suna Kondakci was a visiting assistant professor at the Industrial Engineering Department, Purdue University, when the paper was revised.     

BiLevel programming Data Envelopment Analysis with constrained resource

A new BiLevel programming Data Envelopment Analysis (DEA) approach is created to provide valuable managerial insights when assessing the performance of a system with Stackelberg-game relationships. This new approach allows us to evaluate the firm performance in decentralized decisions, which consist of the objective(s) of the leader at its first level and that is of the follower at the second level. This approach can help decentralized companies to optimize their performance using multiple inputs to produce multiples outputs in a cost-effective way, where both the system “black-box” and subsystem performance are exposed in details. We show the algorithms and solutions to our new models. We illustrate and validate the proposed new approach using two case studies: a banking chain and a manufacturing supply chain. The computation shows that subsystem being efficient at all levels results in an overall efficiency achievement in a decentralized BiLevel structure.     

Critical path analysis and resource constrained project scheduling — Theory and practice

Critical path techniques have been in documented use since the mid 1950's and are now widely used in most aspects of project planning and control. Interest in this area in recent years has been mainly concerned with making the best use of scarce resources throughout the duration of a project and a considerable amount of work has been undertaken in this area by both theorists and practitioners in project management. There is still however an apparent gap between the published theoretical work and the requirements of project schedulers and managers in the field and this paper briefly describes the different approaches taken, how they differ and suggests where future effort may be directed.     

A simulated annealing algorithm for resource constrained project scheduling problems

This paper presents a simulated annealing algorithm for resource constrained project scheduling problems with the objective of minimising makespan. In the search algorithm, a solution is represented with a priority list, a vector of numbers each of which denotes the priority of each activity. In the algorithm, a priority scheduling method is used for making a complete schedule from a given priority list (and hence a project schedule is defined by a priority list). The search algorithm is applied to find a priority list which corresponds to a good project schedule. Unlike most of priority scheduling methods, in the suggested algorithm some activities are delayed on purpose so as to extend search space. Solutions can be further improved by delaying certain activities, since non-delay schedules are not dominant in the problem (the set of non-delay schedules does not always include an optimal solution). The suggested algorithm is flexible in that it can be easily applied to problems with an objective function of a general form and/or complex constraints. The performance of the simulated annealing algorithm is compared with existing heuristics on problems prepared by Patterson and randomly generated test problems. Computational results showed that the suggested algorithm outperformed existing ones.     

Computing redundant resources for the resource constrained project scheduling problem

Several efficient lower bounds and time-bound adjustment methods for the resource constrained project scheduling problem (RCPSP) have recently been proposed. Some of them are based on redundant resources. In this paper we define redundant functions which are very useful for computing redundant resources. We also describe an algorithm for computing all maximal redundant functions. Once all these redundant functions have been determined, we have to identify those that are useful for bounding. Surprisingly, their number is reasonable even for large resource capacities, so a representative subset of them can be tabulated to be used efficiently. Computational results on classical RCPSP instances confirm their usefulness.     

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.     

Multi-criteria approximation schemes for the resource constrained shortest path problem

In the resource constrained shortest path problem we are given a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resources with finite budget limits. A minimum cost source-destination path is sought such that the total consumption of the arcs from each resource does not exceed its budget limit. In the case of constant number of weight functions we give a fully polynomial time multi-criteria approximation scheme for the problem which returns a source-destination path of cost at most the optimum, however, the path may slightly violate the budget limits. On the negative side, we show that there does not exist a polynomial time multi-criteria approximation scheme for the problem if the number of weight functions is not a constant. The latter result applies to a broad class of problems as well, including the multi-dimensional knapsack, the multi-budgeted spanning tree, the multi-budgeted matroid basis and the multi-budgeted bipartite perfect matching problems.     

A distributed exact algorithm for the multiple resource constrained sequencing problem

Sequencing problems arise in the context of process scheduling both in isolation and as subproblems for general scenarios. Such sequencing problems can often be posed as an extension of the Traveling Salesman Problem. We present an exact parallel branch and bound algorithm for solving the Multiple Resource Constrained Traveling Salesman Problem (MRCTSP), which provides a platform for addressing a variety of process sequencing problems. The algorithm is based on a linear programming relaxation that incorporates two families of inequalities via cutting plane techniques. Computational results show that the lower bounds provided by this method are strong for the types of problem generators that we considered as well as for some industrially derived sequencing instances. The branch and bound algorithm is parallelized using the processor workshop model on a network of workstations connected via Ethernet. Results are presented for instances with up to 75 cities, 3 resource constraints, and 8 workstations.     

Worker deployment in dual resource constrained systems with a task-type factor

This paper investigates worker learning and forgetting phenomenon in a dual resource constrained system (DRC) setting. Worker learning and forgetting in two and three stage DRC systems are modeled according to the dual-phase learning and forgetting model (DPLFM), which is based on the theory that a task has separate cognitive and motor requirements. Results show that the task-type (with respect to its learning rate and proportion of cognitive and motor requirements) affects the performance of training and deployment policies in DRC systems, and as such it should be included in future DRC research.     

Multiple q-Mahler measures and zeta functions

We introduce multiple q-Mahler measures and we calculate some specific examples, where multiple q-analogues of zeta functions appear. We study also limits as the multiple q goes to 1.     

The incorporation of target performance measures and constrained optimisation in the newsboy problem

The solution of the classical Newsboy problem requires some knowledge of the costs of wastage as well as the costs of lost opportunity. Such knowledge is often hypothetical and generally unavailable. More readily available knowledge, particularly in complex organisations, often relates to targets for wastage and availability, especially where perishable goods are involved. These targets can be incorporated effectively into a generalised forecasting context with a broad distribution of demand patterns by the use of a formulated statistic that measures the suitability of the data for the achievement of such targets. The paper proposes a model and algorithm for optimising supply levels using these two performance measures and constrained optimisation of a target gain function.     

Accelerated label setting algorithms for the elementary resource constrained shortest path problem

A label setting algorithm for solving the Elementary Resource Constrained Shortest Path Problem, using node resources to forbid repetition of nodes on the path, is implemented. A state-space augmenting approach for accelerating run times is considered. Several augmentation strategies are suggested and compared numerically.     

A computational study of solution approaches for the resource constrained elementary shortest path problem

We present the results of a computational investigation of solution approaches for the resource constrained elementary shortest path problem ( $\mathcal{RCESPP}$ ). In particular, the best known algorithms are tested on several problem instances taken from literature. The main aims are to provide a detailed state of the art and to evaluate methods that turn out to be the most promising for solving the problem under investigation. This work represents the first attempt to computationally compare solution approaches for the $\mathcal{RCESPP}$ .     

A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows

We consider a project scheduling problem where a number of tasks need to be scheduled. The tasks share resources, satisfy precedences, and all tasks must be completed by a common deadline. Each task is associated with a cash flow (positive or negative value) from which a “net present value” is computed dependent upon its completion time. The objective is to maximize the cumulative net present value of all tasks. We investigate (1) Lagrangian relaxation methods based on list scheduling, (2) ant colony optimization and hybrids of (1) and (2) on benchmark datasets consisting of up to 120 tasks. Considering lower bounds, i.e., maximizing the net present value, the individual methods prove to be effective but are outperformed by the hybrid method. This difference is accentuated when the integrality gaps are large.     

Solving the resource constrained deadline scheduling problem via reduction to the network flow problem

In this paper the problem of the equivalence of scheduling tasks on processors with the presence of deadlines and additional resources and the network flow problem is studied. This equivalence permits it to be proven that the problem of finding a maximal flow in a binary network with multipliers equal to 1 or 2 is NP-complete.     

Examination of flexibility acquisition policies in dual resource constrained job shops with simultaneous worker learning and forgetting effects

This study investigates worker training related issues in dual resource constrained (DRC)job shop environments with the simultaneous presence of learning, forgetting (which causes relearning) and worker attrition effects. Learning and forgetting occurs as workers are trained in different departments on the shop floor. A recent survey of job shops based in the US indicates that firms are concerned about the relearning losses that accompany worker transfers, and are using a variety of strategies to reduce the effects of relearning. This study uses the learn-forget-learn (LFL) model to capture different learning and forgetting environments in order to understand whether up-front training can be used to reduce relearning and realize the benefits of worker flexibility. Results show that the existing forgetting rate has a significant impact on inventory and customer service performance. Extensive up-front training helps reduce relearning, however, it does not always help improve performance.     

Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

This paper presents a unified three-stage approach (TSA), comprising preprocessing, setup, and iterative solution stages, for solving several variations of the resource constrained shortest-path problem (RCSP). TSA is designed specially for column-generation applications in which sub-problems must be solved repetitively. The first two stages are implemented one time and only the third stage need be applied repetitively. In a companion paper, the authors proposed a TSA for solving RCSP on an acyclic graph with upper bound resource-limitation constraints. This paper shows that a TSA can be designed to solve each of several related problems: shortest-path with equality resource-limitation constraints; shortest-path with resource windows; resource-constrained, k-shortest path; and multiple-resource, multiple-choice knapsack. A numerical example demonstrates application of a TSA to design an international assembly system and its supply chain using branch and price with multiple-choice knapsack sub-problems. Computational results show that our TSA can solve this sub-problem effectively in such a column-generation environment.     

Bridging the gap between self schedules and feasible schedules in staff scheduling

Every company that has employees working on irregular schedules must deal with the difficult and time consuming problem of creating feasible schedules for the employees. We introduce an algorithm that takes a partial schedule created by requests from employees and creates feasible schedule where most of the employee’s requests are unchanged, while still making sure that rules and regulations are not violated. The algorithm is based on independent modules, which can be executed in any order, and each module tries to emulate some action taken by a staff manager. Our goal is to create a transparent and fair system that creates feasible schedules of high quality, but also a system where the employees can get an explanation and justification for every change that the algorithm makes to the employee requests. By emulating the actions of staff managers, the algorithm is easily understood by staff managers and, using detailed logs of any action, make any decision easy to explain to the employees. We will present the algorithm and show results from four real world companies and institutions. The results show that a simple module based heuristic can get good results and create fair and feasible schedules that encourage employees to participate in the self-scheduling process.