A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

Knowledge based-system for alternative design,cost estimating and scheduling

The traditional design, cost estimating and scheduling procedures focus on assessing costs and schedule after design decisions are made and conveyed to construction drawings and design that is, they do not have a mechanism that allow the designer to perform a rapid ‘what if’ analysis on design alternatives and cost analysis of different types of building materials and alternative schedule analysis at early stage of project without accompanying of detailed design and drawing. Moreover, the available scheduling tools are not integrated to design and cost estimating system and hence require manual input of activities lists, activities sequencing, resources, costs and durations to generate project schedule and they are unable to consider the effect of productivity factors and the resulting uncertainty inherent in each activity. This paper presents an integrated knowledge based system for construction cost estimating and scheduling. The knowledge based system supports an automated alternative design analysis with on line schematic drawing, material selection, crew selection and productivity analysis for generating activities sequencing, normal durations, productivity adjusted durations, cost estimate, list of materials selected and their respective quantities and list of assigned crew. An analysis of alternative design, cost estimating and scheduling for a residential building using the integrated system is presented.     

An integrated approach for requirement selection and scheduling in software release planning

It is essential for product software companies to decide which requirements should be included in the next release and to make an appropriate time plan of the development project. Compared to the extensive research done on requirement selection, very little research has been performed on time scheduling. In this paper, we introduce two integer linear programming models that integrate time scheduling into software release planning. Given the resource and precedence constraints, our first model provides a schedule for developing the requirements such that the project duration is minimized. Our second model combines requirement selection and scheduling, so that it not only maximizes revenues but also simultaneously calculates an on-time-delivery project schedule. Since requirement dependencies are essential for scheduling the development process, we present a more detailed analysis of these dependencies. Furthermore, we present two mechanisms that facilitate dynamic adaptation for over-estimation or under-estimation of revenues or processing time, one of which includes the Scrum methodology. Finally, several simulations based on real-life data are performed. The results of these simulations indicate that requirement dependency can significantly influence the requirement selection and the corresponding project plan. Moreover, the model for combined requirement selection and scheduling outperforms the sequential selection and scheduling approach in terms of efficiency and on-time delivery.     

Resource‐constrained project scheduling through the goal programming model: integration of the manager's preferences

The aim of this paper is to present a multi‐objective project scheduling approach to help project managers when deciding on a baseline schedule. The concepts of satisfaction functions and goal programming are incorporated to generate this baseline schedule that represents the best compromise among a set of conflicting project objectives. An efficient computerized procedure based on the tabu search algorithm is proposed and enables the handling of large planning and scheduling projects.     

Combining contemporary and traditional project management tools to resolve a project scheduling problem

In this paper we examine a construction project involving the building of large concrete slabs for three buildings in an office park complex. There are finish-to-start (FS) as well as start-to-start (SS) and finish-to-finish (FF) precedence relationships among the project activities. We prepare an initial project schedule using Microsoft Project and manually validate the results using the precedence diagramming method (PDM) procedure. When the client informs us that the schedule must be shortened we find that Microsoft Project does not have the capability for resolving our particular time/cost tradeoff issues. So we revert to the traditional approach for resolving time/cost tradeoffs in projects and develop an original linear programming formulation for the time/cost tradeoff problem when a project is modeled as a precedence diagram. By combining contemporary (Microsoft Project) and traditional (a linear programming time/cost tradeoff model) project management tools we are able to successfully resolve the scheduling issues associated with the slab construction project. Further, we demonstrate the anomalous effects of start-to-start (SS) and finish-to-finish (FF) relationships via our construction project example in which the solution to the time/cost tradeoff problem requires that certain activities be lengthened in order to shorten the project duration.     

(DP)SM: A dynamic approach to resouce constraint project scheduling

The purpose of this paper is twofold, first to introduce and evaluate a dynamic priority scheduling model developed in this research for solving the resource constraint project scheduling problem, second to introduce an improvement made upon the first model by cross breeding Dynamic Programming with the Dynamic Priority Scheduling Method (DPSM). The second model called Dynamic Priority Dynamic Programming Scheduling Method [(DP)²SM] aims at optimising the staged resource allocation decisions in DPSM. DPSM divides a project into phases (cycles) the length of which depend on the duration of the project and the period of clock cycle selected. The scheduling process starts by allocating resources to the first phase/cycle using a variety of policies, then the best schedule is selected based on an objective function. The process continues till all the activities are scheduled. In DPSM the interaction between phases is ignored while the decisions of each phase or cycle will affect all the remaining phases. Using (DP)² SM it may be possible to improve the quality of a schedule and reduce the duration of a project by optimising the overall project schedule.     

Simulating the dynamic scheduling of project portfolios

A main challenge in project management is to provide methodologies that facilitate coordination among the projects in a portfolio or in a firm. Each incoming project in an existing portfolio affects its schedule, the resources availability and the planned performance. There are no analytical solutions for the problem of dynamic scheduling of resources for multiple projects in real time. Mathematical approaches, like integer programming or network based techniques, cannot describe the complexity of real problems (multi-projects environments have many interrelated elements), and have difficulties to adapt the analysis to dynamic changes.We propose a multi-agent system, where projects negotiate the procurement of resources through an auction mechanism all over the portfolio life. Both, projects and resources are modelled as agents. Projects demand resources for fulfilling their scheduled planned work, whereas resources offer their capabilities and workforce. This framework allows project portfolio management and the assessment in the decision of acceptance/rejection new projects.     

人工蜂群算法求解资源受限项目调度问题

针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。     

考虑胜任力水平的研发项目群人力资源调度

在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限项目调度问题模型,该模型是对传统多模式资源约束项目调度问题（MRCPSP）更接近研发项目群实际的扩展。提出了衡量人员胜任力的参数及估算公式,以多项目总工期和总成本最小化为双目标,建立相应的数学优化模型。按双目标重要性排序,依次对工期最优及成本最优的单目标优化问题求解。根据模型的约束条件将多项目初始网络图转化为几种单项目初始网络图,利用枚举算法给出满足约束条件的可行解集,再设计基于动态规划思想的算法进行分阶段寻优。数值实验表明,考虑了胜任力差异的数学优化模型在求解质量方面具有良好性能。     

基于蚁群算法的建设项目赶工措施控制研究

通过讨论资源受限项目调度问题的约束条件、工序实施模式的函数表达及工序工期与工序成本之间的关系,建立了以项目工期-成本最优化为目标的多工序交叉作业赶工措施（MCAM）控制模型;运用引入精英策略的蚁群算法（ACA）结合串行进度生成机制,以某项目标准层施工为例,最终得到可行项目进度计划,并通过与其他算法比较,证明了ACA求解MCAM模型结果合理,算法高效。     

基于关键链的资源受限项目调度新方法

针对资源受限项目调度问题（RCPSPs）的实际需求建立了多目标优化调度模型,综合运用现有研究成果,设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划,再在该计划中嵌入输入缓冲和项目缓冲,保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验,结果表明本文方法较传统项目调度方法有很大改进,论文最后对仿真结果进行了深入讨论,并指出了未来的研究方向。     

An Optimization-Based Approach for Design Project Scheduling

Concurrent engineering has been widely used in managing design projects to speed up the design process by concurrently performing multiple tasks. Since the progress of a design task often depends on the knowledge about other tasks and requires effective communication, tasks and communication activities need to be properly coordinated to avoid delays caused by waiting for information or the need for rework. This paper presents a novel formulation for design project scheduling with explicit modeling of task dependencies and the associated communication activities. General dependencies are modeled as combinations of three basic types representing sequential, concurrent, and independent processes. Communication activities are also modeled as tasks, and their interactions with design tasks are described by sets of intertask constraints. The objective is to achieve timely project completion with limited resources. To improve algorithm convergence and schedule quality, penalties on the violation of constraints coupling design tasks are added to the objective function. A solution methodology that combines Lagrangian relaxation, dynamic programming, and heuristic is developed to schedule design and communication tasks, and a surrogate optimization framework is used to overcome the “inseperability” caused by nonadditive penalties. A heuristic procedure is then developed to obtain scheduling policies from optimization results and to dynamically construct schedules. Numerical results show that the approach is effective to handle various task dependencies and the associated communication activities to provide high-quality schedules.      

An integer programming approach to the multimode resource-constrained multiproject scheduling problem

The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resource-constrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.     

An integrated aircraft routing,crew scheduling and flight retiming model

In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times for crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and crew pairings.     

Modeling dynamic construction work template from existing scheduling records via sequential machine learning

Today, construction planning and scheduling is almost always performed manually, by experienced practitioners. The knowledge of those individuals is materialized, maintained, and propagated through master schedules and look-ahead plans. While historical project schedules are available, manually mining their embedded knowledge to create generic work templates for future projects or revising look-ahead schedules is very difficult, time-consuming and error-prone. The rigid work templates from prior research are also not scalable to cover the inter and intra-class variability in historical schedule activities. This paper aims at fulfilling these needs via a new method to automatically learn construction knowledge from historical project planning and scheduling records and digitize such knowledge in a flexible and generalizable data schema. Specifically, we present Dynamic Process Templates (DPTs) based on a novel vector representation for construction activities where the sequencing knowledge is modeled with generative Long Short-Term Memory Recurrent Neural Networks (LSTM-RNNs). Our machine learning models are exhaustively tested and validated on a diverse dataset of 32 schedules obtained from real-world projects. The experimental results show our method is capable of learning planning and sequencing knowledge at high accuracy across different projects. The benefits for automated project planning and scheduling, schedule quality control, and automated generation of project look-aheads are discussed in detail.     

一种改进的小矩阵连乘算法

首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。     

用Lagrangian松弛法解化工批处理调度问题

研究基于Lagrangian松弛法的化工批处理过程的调度方法.建立了化工批处理过程调度问题的一种混合整数规划(MILP)模型,并通过松弛离散变量和连续变量共存的约束,将问题分解为一个两层次的优化问题,其中上层是原问题的对偶问题,下层由两个子问题构成:一个与产品批量有关,另一个确定操作时间表,分别用线性规划和动态规划方法解这两个子问题.然后从对偶问题的解构作原问题的可行解.数值试验结果证明了该方法的有效性.     

基于Q学习的受灾路网抢修队调度问题建模与求解

受损路网的修复是灾害应急响应中的一个重要环节, 主要研究如何规划道路抢修队的修复活动, 为灾后救援快速打通生命通道.本文首先构建了抢修队修复和路线规划的数学模型, 然后引入马尔科夫决策过程来模拟抢修队的修复活动, 并基于Q学习算法求解抢修队的最优调度策略.对比实验结果表明, 本文方法能够让抢修队从全局和长远角度实施受损路段的修复活动, 在一定程度上提高了运输效率和修复效率, 可以为政府实施应急救援和快速安全疏散灾民提供有益的参考.     

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.