A heuristic approach for resource constrained project scheduling with uncertain activity durations

In this paper, we address the resource constrained project scheduling problem with uncertain activity durations. Project activities are assumed to have known deterministic renewable resource requirements and uncertain durations, described by independent random variables with a known probability distribution function. To tackle the problem solution we propose a heuristic method which relies on a stage wise decomposition of the problem and on the use of joint probabilistic constraints.     

A Lagrangian heuristic for satellite range scheduling with resource constraints

The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred.     

一种新的项目调度解表示方法

基于解集合的准启发式方法是解决资源约束下项目调度问题的有效方法,解的表示形式一直是这种方法的一个重要研究问题。只有充分利用解的形式和目标函数之间的联系,才可能达到在少数枚举下得到尽可能好的解。详细分析了解空间性质,提出了用额外关系表示一个可行解的方法,给出了这种表示方法的理论依据。并介绍了用该方法产生邻域的方法。     

A flexible heuristic for a multi-mode capital constrained project scheduling problem with probabilistic cash inflows

We consider housing projects where an initial capital covers activity expenditures in the starting phase of the project and then, customers who arrive randomly over the project span provide the necessary funds for continuation. The goal is to maximize financial returns, i.e., the project Net Present Value (NPV). Here, capital is considered as a limited nonrenewable resource which is reduced by activity expenditures and augmented by the sales of flats. Activities may be carried out in different operating modes with different durations. The total cost of an activity is fixed irrespective of its operating mode. Thus, the rate of activity expenditures differ from mode to mode. As the previous scheduling decisions are the only controllable factors affecting the available capital at any period, it is important to adjust the speed of expenditures, namely, to select the correct activity modes. The contractor, never sure of the timing of the cash inflows, has to schedule the activities in modes which do not lead to financial bottlenecks and at the same time he has to deliver the project on time. The contractor may also borrow capital from an external source. We propose a flexible heuristic algorithm for solving the capital constrained mode selection problem where there exist general precedence relationships among activities and the magnitude of precedence lags depend on the specific activity mode selected. The algorithm is flexible in the sense that different mode selection criteria are utilized at different decision times depending on the cumulative progress of the project and on some parameters controlled by the contractor. The proposed algorithm may be used as a simulation tool to adjust parameters before the project starts or it may be used as a scheduler during the progress of the project given the current financial situation and cumulative project work done. We test the algorithm by using a typical housing project with real data and also by using hypothetical test problems. The results indicate that the schedules generated are satisfactory with regard to meeting the target project due date and maximizing NPV.     

CIGI2011: A heuristic method for resource-constrained project scheduling with activity overlapping

The overlapping of activities is a common practice to accelerate the execution of engineering projects. This technique consists in executing in parallel two activities, normally executed in a sequential way, by allowing the downstream activity to start before the end of the upstream activity based on preliminary information. In this paper, we propose a constructive heuristic for the resource-constrained project scheduling problem with overlapping modes (RCPSP-OM). Given a set of activities to execute, the RCPSP-OM consists in determining the order of execution in time of a set of activities so as to minimize the total project duration, while respecting precedence relations, resource constraints and overlapping possibilities. The heuristic implies that rework tasks related to overlapping are added to downstream activities and that the consumption of the resources is constant throughout the execution of the project (including rework). The method also considers that the possible overlapping modes for every couple of activities and the duration of rework tasks associated with every mode are known in advance. Results show that, when the objective consists in minimizing the project duration, the consideration of the costs associated to activity overlapping allows to significantly reducing the cost of reworks. On the other hand, when the objective consists in maximizing the gains related to the project execution, the search for the best trade-off between acceleration and increase of project costs enables to avoid losses.     

A heuristic algorithm for group scheduling

Group technology is a rapidly developing productivity improvement tool that can have a significant impact on the development of totally integrated manufacturing facilities and flexible manufacturing systems. Production scheduling associated with group technology is called “Group Scheduling”. There are many heuristic algorithms developed for general job shop applications based on unrealistic hypothesis, complicated computations etc., which are not addressed to group scheduling. In this paper, from the existing algorithms for group scheduling, a heuristic algorithm has been developed and programmed for computer/microcomputer applications. The developed algorithm has been used to determine the optimal group and the optimal job sequence for a batch type production process with functional layout. The developed algorithm is far simpler and easier to compute, compared to the other similar heuristic algorithms and certainly in comparison to other optimization methods such as branch and bound method.     

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

离散人工蜂群算法求解资源时变的项目调度问题

针对资源量随时间变动的项目调度问题提出了一种新的离散人工蜂群求解算法。算法食物源的位置采用基于任务排列的编码方法,并提出一种可以保持解的离散性和可行性的候选食物源生成方法。仿真结果表明,该算法能有效地求解资源时变的受限项目调度问题,研究发现在保持资源总量不变甚至减少的情况下,通过调整资源配置能够显著缩短项目工期,可见资源配置优化在项目管理中的重要作用。     

不确定资源约束下项目鲁棒性调度算法*

在跨企业项目中,由于资源可用时间具有不确定性,从而使得项目计划具有易变性。针对这一问题,首先采用模糊集对项目的不精确时间参数和资源不确定性进行了表示,并在同时考虑调度的质量鲁棒性和解的鲁棒性情况下,定义了调度的鲁棒性度量,进而开发了遗传算法来求解不确定资源约束下的项目鲁棒性调度问题。最后,给出了应用实例,并通过仿真分析说明算法的有效性。该算法已被应用到跨企业项目管理系统中,获得了良好的效果。     

A heuristic approach to batching and scheduling a single machine to minimize setup costs

In this paper we consider the problem of creating batches of parts, to be processed in a flexible manufacturing cell, and scheduling their operations. We consider the case in which the system consists of one machine and at most k parts may be present in the system at the same time. Given that each part requires a sequence of operations, and each operation requires a given tool, the objective is to minimize the total number of setups. We develop a heuristic algorithm for its solution and we present an extensive computational experience.     

Uncertain project scheduling problem with resource constraints

Project scheduling problem is to make a schedule for allocating the loans to a project such that the total cost and the completion time of the project are balanced under some constraints. This paper presents an uncertain project scheduling problem, of which both the duration times and the resources allocation times are uncertain variables. An uncertain programming model with multiple objectives is obtained, whose first objective is to minimize the total cost, and second objective is to minimize the overtime. Genetic algorithm is employed to solve the proposed uncertain project scheduling model, and its efficiency is illustrated by a numerical experiment.     

A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs

This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm.     

A branch and cut heuristic for a runway scheduling problem

The paper is focused on one of the major air traffic management problem that consists in sequencing and scheduling airplanes landing and taking off on a runway. This difficult practical task is still carried out by flight controllers manually with little help from decision support systems. In this paper we propose an approach based on a time indexed integer programming formulation. The formulation is solved with a branch and cut method combined with some heuristic rules for dimension reduction. The effectiveness of the proposed approach is illustrated by computational experiments on real-life problem instances for the Milano Linate airport.     

Robust optimization models for project scheduling with resource availability cost

We address a project scheduling problem with resource availability cost for which the activity durations are uncertain. The problem is formulated within the robust optimization framework, where uncertainty is modeled via a set of scenarios. The proposed solution method is based on the scatter search methodology and employs advanced strategies, such as dynamic updating of the reference set, a frequency-based memory mechanism, and path relinking. A multistart heuristic was also developed and comparative results are reported. The tradeoffs for risk-averse decision makers are discussed.     

Simple and integrated heuristic algorithms for scheduling tasks with time and resource constraints

We consider the problem of scheduling a set of n tasks in a system having r resources. Each task has an arbitrary, but known, processing time and a deadline, and may request use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this article, we study algorithms used for determining whether or not a set of tasks is schedulable in such a system, and if so, determining a schedule for it. This scheduling problem is known to be NP-complete and hence we methodically study a set of heuristics that can be used by such an algorithm. Due to the complexity of the problem, simple heuristics do not perform satisfactorily. However, an algorithm that uses combinations of these simple heuristics works very well compared to an optimal algorithm that takes exponential time complexity. For the combination that performs the best, we also determine the scheduling costs as a function of the size of the task set scheduled.     

A bicriteria approach to minimize maximal lateness and resource consumption for scheduling a single machine

We extend the classical single-machine maximal lateness scheduling problem to the case where the job processing times are controllable by allocating a continuous and nonrenewable resource to the processing operations. Our aim is to construct an efficient trade-off curve between maximal lateness and total resource consumption using a bicriteria approach. We present a polynomial time algorithm that constructs this trade-off curve assuming a specified general type of convex decreasing resource consumption function. We illustrate the algorithm with a numerical example.     

Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem

We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.     

A heuristic method for analyzing driver scheduling problem

A heuristic approach, ZEST for ESTimator, is developed to analyze bus driver scheduling problems and produce an estimate of the number of drivers required for a bus schedule. Based on the observation that the maximum number of drivers is needed in the morning and afternoon peaks, ZEST divides the driver scheduling problem into morning and afternoon subproblems, solves each subproblem separately, and, finally, combines the solutions. The key techniques in ZEST derive from manual scheduling operations that examine the critical decision points in a bus schedule that are vital for a good driver schedule and use these decision points to develop chains of meal breaks that dovetail one driver's meal break with another driver's. ZEST can be used as a standalone estimator of driver duties or as a component of other driver scheduling approaches.     

A compile-time scheduling heuristic for interconnection-constrainedheterogeneous processor architectures

The authors present a compile-time scheduling heuristic called dynamic level scheduling, which accounts for interprocessor communication overhead when mapping precedence-constrained, communicating tasks onto heterogeneous processor architectures with limited or possibly irregular interconnection structures. This technique uses dynamically-changing priorities to match tasks with processors at each step, and schedules over both spatial and temporal dimensions to eliminate shared resource contention. This method is fast, flexible, widely targetable, and displays promising performance     

A heuristic for preemptive scheduling with set-up times

We investigate the problem of preemptively schedulingn jobs onm parallel machines. Whenever there is a switch from processing a job to processing another job on some machine, a set-up time is necessary. The objective is to find a schedule which minimizes the maximum completion time. Form≥2 machines, this problem obviously is NP-complete. For the case of job-dependent set-up times, Monma and Potts derived a polynomial time heuristic whose worst case ratio tends to 5/3 as the number of machines tends to infinity. In this paper, we examine the case of constant (job- and machine-independent) set-up times. We present a polynomial time approximation algorithm with worst case ratio 7/6 form=2 machines and worst case ratio at most 3/2–1/2m form≥3 machines. Moreover, for the casem=2 we construct a fully polynomial time approximation scheme.