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     

Performance analysis of parallel identical machines with a generalized shortest queue arrival mechanism

In this paper we study a production system consisting of a group of parallel machines producing multiple job types. Each machine has its own queue and it can process a restricted set of job types only. On arrival a job joins the shortest queue among all queues capable of serving that job. Under the assumption of Poisson arrivals and identical exponential processing times we derive upper and lower bounds for the mean waiting time. These bounds are obtained from so-called flexible bound models, and they provide a powerful tool to efficiently determine the mean waiting time. The bounds are used to study how the mean waiting time depends on the amount of overlap (i.e. common job types) between the machines.

---

---

Received: February 8, 2000 / Accepted: November 28, 2000     

Resource–constrained project scheduling: a heuristic for the multi–mode case

This paper presents a heuristic solution procedure for a very general resource–constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi–pass priority–rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real–life size with 100 activities and up to 5 modes per activity.

---

---

Received: September 22, 2000 / Accepted: May 18, 2001     

Project scheduling with calendars

For many applications of project scheduling to real-life problems, it is necessary to take into account calendars specifying time intervals during which some resources such as manpower or machines are not available. Whereas the execution of certain activities like packaging may be suspended during breaks, other activities cannot be interrupted due to technical reasons. Minimum and maximum time lags between activities may depend on calendars, too. In this paper, we address the problem of scheduling the activities of a project subject to calendar constraints. We devise efficient algorithms for computing earliest and latest start and completion times of activities. Moreover, we sketch how to use these algorithms for developing priority-rule methods coping with renewable-resource constraints and calendars.

---

---

Received: July 26, 2000 / Accepted: May 15, 2001     

On extreme values of orbit lengths in M/G/1 queues with constant retrial rate

In the design of waiting facilities for the units in a retrial queue, it is of interest to know probability distributions of extreme values of the orbit length. The purpose of this paper is to investigate the asymptotic behavior of the maximum orbit length in the queue with constant retrial rate, as the time interval increases. From the classical extreme value theory, we observe that, under standard linear normalizations, the maximum orbit length up to the nth time the positive recurrent queue becomes empty does not have a limit distribution. However, by allowing the parameters to vary with n, we prove the convergence of maximum orbit lengths to three possible limit distributions when the traffic intensity approaches 1 from below and n approaches infinity.

---

---

Received: October 7, 1999 / Accepted: November 21, 2000     

Developing Strategic Alliances: A Framework for Collaborative Negotiation in Design

This work applies a theory-based framework of collaborative negotiation to some of the disputes that regularly arise during group design. Although the framework was developed to provide general support for group work, this paper focuses on its use as a design tool. The framework, embodied in our system NegotiationLens, has four facets. It: 1. Provides a negotiation method intended to produce gain for all parties. 2. Provides an efficient process for conflict resolution. 3. Develops working alliances. 4. Lets parties decide quickly when they should go their separate ways. The framework produces the above results by: • Helping parties develop well-reasoned and clearly articulated points of view (Adelson and Jordan, 1991; Conklin and Yakemovic, 1991; Conklin and Begeman, 1988; MacLean et al ., 1991). • Creating a context of committment and respect. • Moving negotiating parties away from an adversarial stance and into a collaboration. • Allowing joint construction of solutions that are more beneficial than the unilateral solutions each party initially brought to the table. We present our framework for collaborative negotiation, describe NegotiationLens, and present two cases in which it was used. We present a third case, a large design project with recurrent design conflicts, and argue how NegotiationLens could have been of benefit there.     

Performing Changes in Product Development: A Framework with Keys for Industrial Application

Industrial product development requires continuous improvements in work procedures as a result of constantly changing demands. Support tools have proven to be an oft chosen way to meet new demands; however, few research efforts have been made in how to implement new tools. This article is a contribution to knowledge on carrying out the implementation of support tools. The basis consists of four field studies performed during 1994–1999, containing 78 qualitative research interviews and focusing on the implementation and use of different support tools. A re-analysis has been performed of selected interviews from the field studies, in total 30 interviews. This resulted in recommendations for an implementation framework, consisting of an Implementation Cycle, Organizational Change Field and Managerial Consistence, and five implementation keys: Goal setting, Kowledge Development, Anchoring at All Levels, Suitable Resources and Focus on the Individual.     

Functional Interdependence and Product Similarity Based on Customer Needs

In this paper, related product functions are determined for a group of approximately 70 consumer products. Using customer need data, a new matrix approach is introduced to identify these relationships. Techniques are then created for determining product similarity. These techniques are clarified and validated through three case studies, including beverage brewers and material-removal products. The results of these case studies are argued to have significant impact on design-by-analogy procedures, benchmarking methods, mass customization strategies and modular design. The paper concludes with a discussion of applications and related procedures for product development.     

A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, truncated branch and bound and the solution of a residual problem. We have coded and tested all the combinations of algorithms and rounding procedures. The computational results obtained on a set of randomly generated test problems show their relative efficiency and allow the potential user to choose from among them, according to the available computing time. Rceived: January 9, 2001 / Accepted: December 10, 2001     

Scheduling vehicles in automated transportation systems Algorithms and case study

One of the major planning issues in large scale automated transportation systems is so-called empty vehicle management, the timely supply of vehicles to terminals in order to reduce cargo waiting times. Motivated by a Dutch pilot project on an underground cargo transportation system using Automated Guided Vehicles (AGVs), we developed several rules and algorithms for empty vehicle management, varying from trivial First-Come, First-Served (FCFS) via look-ahead rules to integral planning. For our application, we focus on attaining customer service levels in the presence of varying order priorities, taking into account resource capacities and the relation to other planning decisions, such as terminal management. We show how the various rules are embedded in a framework for logistics control of automated transportation networks. Using simulation, the planning options are evaluated on their performance in terms of customer service levels, AGV requirements and empty travel distances. Based on our experiments, we conclude that look-ahead rules have significant advantages above FCFS. A more advanced so-called serial scheduling method outperforms the look-ahead rules if the peak demand quickly moves amongst routes in the system. Received: June 21, 2000 / Accepted: January 22, 2001