A Comparison of Due Date Setting,Resource Assignment,and Job Preemption Heuristics for the Multiproject Scheduling Problem*

This research examines a heuristic, rule-based approach for setting due dates in a multiproject, multijob, or assembly shop. Due date estimation is a challenging problem because the operating environment is capacitated, involves the allocation of multiple resources, and allows for the preemption of resources from one project or job to another. The dynamic, continuous arrival of new jobs or orders frequently results in the preemption of resources through the application of managerially determined priority policies. These preemption policies have a significant impact on the ultimate completion time of a job or a project. A three-factor, full-factorial computer simulation experiment is used to assess the relative effectiveness of combinations of four due date setting heuristics, five resource assignment heuristics, and three resource preemption heuristics. Recommendations are made for the selection of due date and resource assignment heuristic combinations under the three preemption policies examined.     

Effects of Erroneous Estimation of Activity Durations on Scheduling and Dispatching a Single Project*

This research examines the effects of erroneous estimation of activity durations on two different approaches for executing a resource-constrained project. The two approaches are scheduling and dispatching. This research is conducted in two phases. Phase one examines the performance of scheduling and dispatching rules in a variety of project environments. These project environments are categorized by three different factors, namely, the order strength of the precedence relationship, the level of resource availability and the size of errors in estimating the activity durations. The results show that scheduling generally produces a shorter project completion time than the heuristic dispatching rules. The results also indicate that project environment affects only the relative performance differences of the scheduling and dispatching rules but not their ranking. Phase two examines the effect of rescheduling. The results show that frequent rescheduling improves the project completion time, while the timing of rescheduling has little impact on the improvement in the project completion time. The results also identify the project environments where rescheduling is beneficial.     

随机抽样算法在多项目调度中的应用

针对资源约束下的多项目调度问题,扩展了单项目进度生产机制,并在此基础上设计了多项目调度的随机抽样算法。通过对比分析,说明不同的任务优先规则对随机抽样算法具有不同的影响,其中采用MINSLK等优先规则的随机抽样算法能够有效地缩短项目平均工期。与其他多项目调度启发式算法的比较和统计检验,说明随机抽样算法显著优于这些常用的启发式算法。     

RESOURCE PLANNING FOR MULTIPLE PROJECTS *

This paper is concerned with the estimation of the resource requirements to service multiple projects that use many types of resources. It reports on a systematic procedure to determine the low cost levels of these resources, focusing on the two following characteristics: (1) the comparative cost of standard time to overtime in the utilization of these resources for the economical completion of the projects, and (2) the impact of highly expensive equipment in the determination of the economic levels of the manpower resources that combine with the equipment to form a crew. A numerical example is also presented to illustrate the method. Resource planning is of particular interest in the area of multiproject scheduling, since most of the commonly utilized heuristic solution approaches focus on the allocation of a limited set of available resources. In the corporate strategic planning functions, resource planning is particularly important for capital investment, training and development, and procurement scheduling.     

Supporting Quick Response Through Scheduling of Make-to-Stock Production/Inventory Systems*

Scheduling of traditional job shops in make-to-order systems has seen extensive research over the past three decades. In such systems, performance is often related to various job completion metrics such as average flow time, average lateness, etc. This paper examines a scheduling problem in a make-to-stock environment where individual job completion measures are irrelevant. In this case, customer orders are satisfied through on-hand inventory where customer service is more closely related to the manufacturer's ability to quickly satisfy demand. We consider the role of scheduling in reducing inventories and improving customer service in the context of a manufacturer who assembles several different products on a single assembly line. We develop scheduling rules for such a system and experimentally compare their performance to those typically used in such environments. Our results indicate that rules which consider the inventory position and demand forecast outperform traditional fixed cycle rules.     

A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations

This research examines the performance of 13 dispatching rules for executing a resource-constrained project whose estimated activity durations may differ from the actual activity durations. The dispatching rules are tested in environments characterized by three factors, namely, the order strength of the precedence relationship, the level of resource availability and the level of estimation errors in the activity durations. The results show that project environment affects only the performance differences but not the grouping of the better dispatching rules. The greatest number of successors, rank positional weight, greatest cumulative resource requirement and minimum activity slack dispatching rules consistently perform better than the other dispatching rules, unaffected by the accuracy of the estimated activity durations. This finding validates the results of many past studies in the deterministic project environment for choosing the right dispatching rule for both projects with and without well-estimated activity durations.     

资源约束下多项目调度的改进遗传算法

针对资源约束下的多项目调度问题,在前人提出的有效的启发式算法研究路径基础上,本文利用遗传算法,结合进度生成机制,提出了多项目调度的改进遗传算法。与其他多项目调度启发式算法相比,该算法在平均项目延迟和最佳解比例方面都表现较好,综合利用优化后的优先规则也使得该算法更适用于不同网络复杂度和不同资源约束程度的多项目调度问题中。     

Control of interrelated research and development projects

The purpose of this paper is to examine a type of resource allocation problem arising in the context of research and development activities. The particular problem analyzed involves scheduling a group of projects in such a way that total cost is minimized while several precedence relations are satisfied and specific completion times are maintained. The primary difficulty results from the existence of commonalities that allow the successful completion of a particular project to be applied to several different purposes. A solution approach is developed which combines a one-pass network algorithm to deal with the precedence and time restrictions and a dynamic programming procedure to allocate the resources to each project.     

An Investigation of Scheduling Policies in a Dual-Constrained Manufacturing Cell*

In previous group scheduling studies, labor has essentially been ignored by assuming that enough labor is assigned to each machine in the cell. In reality, however, management usually does not have the resources to employ a laborer at each machine in the cell (i.e., machines need to share labor). Both labor scheduling and group scheduling heuristics need to be administered to manage the cell effectively. This study develops and examines scheduling procedures for a dual-constrained (i.e., machine and labor) manufacturing cell. Eleven decision rules are developed and tested under 16 different experimental conditions. The experimental factors used are interarrival time distribution, cell load, setup-to-run-time ratio, and transfer-to-run-time ratio. Results show that interarrival time distribution and cell load have the greatest impact on the performance of the cell. This suggests that effective production planning aimed at reducing job arrival variation and leveling the cell load can substantially improve cell performance. Among the experimental factors, setup and transfer-to-run-time ratio factors had the strongest influence on the rankings of the decision rules. These rankings were fairly robust across all experimental conditions and performance measures. The results also indicated that the inclusion of labor as a contraint in the cell had a significant impact on the performance of several group scheduling heuristics. Finally, it was shown that the best performing decision rules consider both transfer time and subfamily setup times.     

A HEURISTIC ALGORITHM FOR RESOURCE LEVELING IN MULTI-PROJECT,MULTI-RESOURCE SCHEDULING

The utility of conventional project management techniques, such as PERT and CPM, is hampered by significant and realistic network attributes and managerial considerations. There are many situations which involve more than one project and numerous resources. Of major concern in such situations is the reduction of the maximum quantity of each required resource. The algorithm presented here is capable of scheduling the individual activities in multiple projects with multiple resources and leveling the overall quantity of each resource which is required. The basis of the algorithm is a sequencing procedure for examining various combinations of activity start times. The measure of effectiveness for each combination is the sum of the squares of the required quantity of each resource in each time period.     

随机多模式资源受限项目调度

项目调度是实现项目资源优化配置的重要手段。项目执行时往往面临大量不确定因素,并呈现出典型的多模式特性,给项目调度带来了很大挑战。鉴于此,本文研究活动工期不确定条件下的多模式资源受限项目调度问题,建立了该问题的马尔科夫决策过程模型。为了高效求解上述模型,设计了基于Rollout的近似动态规划算法。该算法可以在项目执行过程中根据最新的项目状态动态给出调度方案,从而有效优化项目期望工期。在所提算法中,利用“活动—模式”列表与并行调度机制相结合的启发式算法构建基准策略,并设计了基于离散时间马尔科夫链的动态仿真,以进一步提升算法性能。基于公开的项目调度问题库PSPLIB,通过大规模计算实验分析了本文算法的性能,探讨了多种因素对调度效果的影响。     

Managing a Portfolio of Product Development Projects under Resource Constraints

Managers of product development (PD) project portfolios face difficult decisions in allocating limited resources to minimize project or portfolio delay. Although PD projects are highly iterative (cyclical), almost all of the vast literature on project scheduling assumes that projects are acyclical. This article addresses this gap with a comprehensive analysis of 31 priority rules (PRs) on 18,480 portfolios containing 55,440 iterative projects. We find that the best PRs for iterative project portfolios differ significantly from those for acyclical ones, and that the best PRs at the project level differ from those at the portfolio level. The best PR depends on project and portfolio characteristics such as network density, iteration intensity, resource loading profile, and amount of resource contention. In particular, by amplifying the effects of iteration, high‐density networks hold dramatically different implications for iterative projects. Moreover, the best PR also differs depending on whether the objective is to minimize the average delay to all projects or to minimize delay to the overall portfolio. Thus, a project or portfolio manager who uses the same PR on all occasions will exhibit unnecessarily poor performance in most cases.     

基于拍卖机制的资源转移时间型动态分布式多项目调度

实践中,企业并行实施地域上分散的多个项目时,资源在各子项目之间的转移时间是影响多项目整体进度的关键因素,同时在动态多项目环境下,新项目不断到达且到达时间不可预知使得制定多项目调度计划遭遇更大困难。本文在动态环境下对资源转移时间型分布式多项目调度问题进行建模和求解,基于多代理系统建立分布式多项目调度问题的动态模型,并将拍卖理论引入其中,设计一种基于时间窗拍卖机制的分布式多代理系统(DMAS/ATW),在动态环境和资源转移时间约束下为多项目配置全局资源。通过一个具体的分布式多项目示例详细分析DMAS/ATW算法的动态调度过程,并基于MPSPLIB中的分布式多项目算例开展数值实验。实验结果表明：无资源转移时间约束时,DMAS/ATW算法求得的平均项目延迟同比相关文献中的DMAS/RIA算法最多减少42%,平均减少26%;有资源转移时间约束时,DMAS/ATW算法对1/3算例集的求解结果优于DMAS/RIA算法在无资源转移时间约束时的结果,验证了本文DMAS/ATW算法求解效果的优异性。对算例规模和全局资源利用系数的实验分析还表明,DMAS/ATW算法对不同规模和资源约束紧张程度的算例都具有良好的适应性。     

Project Scheduling—Theory and Practice

The project scheduling problem involves the scheduling of project activities subject to precedence and/or resource constraints. Of obvious practical importance, it has been the subject of intensive research since the late fifties. A wide variety of commercialized project management software packages have been put to practical use. Despite all these efforts, numerous reports reveal that many projects escalate in time and budget and that many project scheduling procedures have not yet found their way to practical use. The objective of this paper is to confront project scheduling theory with project scheduling practice. We provide a generic hierarchical project planning and control framework that serves to position the various project planning procedures and discuss important research opportunities, the exploration of which may help to close the theory‐practice gap.     

Semi-online scheduling on two identical machines with rejection

In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. In the first problem one can reassign several scheduled jobs in rejection tache, in the second a buffer with length k is available in rejection tache. Two optimal algorithms both with competitive ratio $\frac{3}{2}$ are presented.     

Robust Resource Allocation Decisions in Resource‐Constrained Projects*

The well‐known deterministic resource‐constrained project scheduling problem involves the determination of a predictive schedule (baseline schedule or pre‐schedule) of the project activities that satisfies the finish–start precedence relations and the renewable resource constraints under the objective of minimizing the project duration. This baseline schedule serves as a baseline for the execution of the project. During execution, however, the project can be subject to several types of disruptions that may disturb the baseline schedule. Management must then rely on a reactive scheduling procedure for revising or reoptimizing the baseline schedule. The objective of our research is to develop procedures for allocating resources to the activities of a given baseline schedule in order to maximize its stability in the presence of activity duration variability. We propose three integer programming–based heuristics and one constructive procedure for resource allocation. We derive lower bounds for schedule stability and report on computational results obtained on a set of benchmark problems.     

多项目环境下新产品研发项目资源分配问题研究

在对国内外相关文献进行评述的基础上,针对多项目环境下新产品研发项目的资源分配问题,将新产品研发多项目资源分配转换为一个多队列排队问题,建立了一个仿真模型,并以三个并行新产品研发项目为例,通过GPSS系统仿真得出了新产品研发项目的完工时间和资源分布结果并进行了分析。     

资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制,需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟,因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题,也是排列组合问题,通常难度很大,包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化,即如何将项目中某2n个平行工序调整为n个顺序工序对,并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络）,运用简单的时间参数量化了平行工序顺序化对项目工期的影响,进而降低问题的求解难度,建立了纯0-1规划模型。实验验证了该模型的求解效率,求解100个平行工序规模的问题平均耗时0.2605秒,而求解500个平行工序规模的问题平均耗时10.66秒。     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.