A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

Two basic problems in reliability-based structural optimization

Optimization of structures with respect to performance, weight or cost is a well-known application of mathematical optimization theory. However optimization of structures with respect to weight or cost under probabilistic reliability constraints or optimization with respect to reliability under cost/weight constraints has been subject of only very few studies. The difficulty in using probabilistic constraints or reliability targets lies in the fact that modern reliability methods themselves are formulated as a problem of optimization. In this paper two special formulations based on the so-called first-order reliability method (FORM) are presented. It is demonstrated that both problems can be solved by a one-level optimization problem, at least for problems in which structural failure is characterized by a single failure criterion. Three examples demonstrate the algorithm indicating that the proposed formulations are comparable in numerical effort with an approach based on semi-infinite programming but are definitely superior to a two-level formulation.     

人力资源约束下的项目群调度问题建模与求解

基于人员胜任力是影响工作绩效的关键因素,将资源受限项目调度问题中的可更新资源通过一系列科学合理的方法或者手段转变为存在胜任力差异的人力资源,由此构建起一个强调胜任力差异的人力资源约束项目调度问题模型,此模型最突出的优势在于选取了能够客观合理评估人员胜任力的指标,提供了严谨科学的关系式,将复杂的多项目总工期与总成本的双目标最小化问题转换为综合指标单目标最大化问题,建立数学优化模型,采用遗传算法求解。通过算例研究证实,相较于传统多模式模型,基于人员胜任力水平差异的模型明显更胜一筹,其优势集中表现为最优工期更短、最优成本更低。考虑了胜任力差异的数学优化模型更符合研发项目群管理实践,同时遗传算法在求解方面不仅效率高,并且更容易获得客观准确的结果。     

An exact algorithm for minimizing resource availability costs in project scheduling

A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available.     

Multiobjective bilevel optimization

In this work nonlinear non-convex multiobjective bilevel optimization problems are discussed using an optimistic approach. It is shown that the set of feasible points of the upper level function, the so-called induced set, can be expressed as the set of minimal solutions of a multiobjective optimization problem. This artificial problem is solved by using a scalarization approach by Pascoletti and Serafini combined with an adaptive parameter control based on sensitivity results for this problem. The bilevel optimization problem is then solved by an iterative process using again sensitivity theorems for exploring the induced set and the whole efficient set is approximated. For the case of bicriteria optimization problems on both levels and for a one dimensional upper level variable, an algorithm is presented for the first time and applied to two problems: a theoretical example and a problem arising in applications.     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

The use of QP-free algorithm in the limit analysis of slope stability

In many mountainous areas, landslides and slope instabilities frequently occur after heavy rainfall and earthquake, and result in enormous casualties and huge economic losses. In order to mitigate the landslides hazard efficiently, a method is required for a better understanding of stability analysis. Fortunately, upper bound theorem of limit analysis provides a practical and effective upper bound approach to evaluate the stability of slopes. And in this approach, the search for the minimum factor of safety can be formulated as a nonlinear constrained optimization. In general, the SQP-type algorithms are used to solve this optimization problem. However, it is quite time consuming and difficult to search the optimum from an arbitrary starting point based on the SQP-type algorithms. Fortunately, a QP-free algorithm based on penalty function and active-set strategy can be globally convergent toward the KKT points with arbitrary starting point, and the rate of convergence is local superlinear or even quadratic. Two classical problems of slope stability are solved by this QP-free algorithm. The results show that the QP-free algorithm would be the better choice than SQP-type algorithms for solving the nonlinear constrained optimization problem which is derived from the upper bound limit analysis of slope stability.     

金属矿山企业生产计划优化方法

针对金属矿山企业的单位开采与运输成本大、优化求解结果偏差大问题, 首先, 依据金属矿山企业编制开采计划的基本原则, 以矿石开采与运输成本最小化为优化目标, 利用整数规划方法, 构建了金属矿山企业生产计划数学模型, 其次, 为了精准快速求解金属矿山企业生产计划模型, 提出了改进的量子粒子群优化算法, 采用进化速度和聚集度因子对算法中的惯性权重进行动态调整, 并设计了双层可行域搜索策略, 提高了算法的局部和全局搜索能力。最后, 以某大型金属矿山企业采运生产作业为案例, 通过与矿山实际生产指标、非线性规划结果以及粒子群优化结果进行比较分析。结果表明:在相同经济指标和参数环境下, 本文算法优于其它两种优化方法, 且每吨矿石的开采和运输成本减少了0.05元左右, 降低了金属矿山企业的开采运输成本, 提高了企业的整体经济效益。     

Cooperation in one machine scheduling

A combinatorial optimization problem can often be understood as the problem to minimize cost in a complex situation. If more than one party is involved, the solution of the optimization problem is not the end of the story. In addition it has to be decided how the minimal total cost has to be distributed among the parties involved. In this paper cost allocation problems will be considered arising from one-machine scheduling under additive and weakly increasing cost functions. The approach of the problem will be game theoretical and we shall in fact show that in many cases the games related to the cost allocation problems are balanced.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Solving the short-term electrical generation scheduling problem by an adaptive evolutionary approach

In this paper, we introduce an adaptive evolutionary approach to solve the short-term electrical generation scheduling problem (STEGS). The STEGS is a hard constraint satisfaction optimization problem. The algorithm includes various strategies proposed in the literature to tackle hard problems with constraints such as: the representation used a non-binary coding scheme that drastically reduces the search space compared with the traditional evolutionary approaches. Specialized operators are especially designed for this problem and for this kind of representation, which also includes a local search procedure. Furthermore, the algorithm is guided by an adaptive parameter control strategy. We used some very well known benchmarks for STEGS to evaluate our approach. The results are very encouraging and we have obtained new better values for all the systems tested. Our aim here is to show that evolutionary approaches can be considered as good techniques to be used to solve real-world highly constrained problems.     

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.     

Schedule-induced posets

Schedules are a basic tool in the treatment of project networks and sequencing problems. For many questions, however, it is not the schedule itself but a partial order (poset) naturally induced on the set of activities that is really relied on. In fact, this correspondence of the usually uncountably many schedules to a finite system of posets was a key to many recent results in this field and constitutes the discrete character of the described problems, all the more so as additional properties of the respective schedules can very often be reflected in related properties of these induced posets.The present paper gives insights into the class of those posets that can be induced by schedules. An immediate observation is that schedule-induced posets are just the interval orders. More involved characterizations are concerned with the possible ‘local optimality’ of such structures. One such property is the existence of activity durations that will result in a project duration of the considered poset that is shorter (simultaneously) than the duration of all its extensions. A similar, related characterization for general regular cost functions (in particular tardiness cost) is also included, as are insights into ‘best’ activity durations with the mentioned properties.The paper closes with some remarks and numerical data on the considered class of posets as a whole.     

A note ‘On a single machine-scheduling problem with separated position and resource effects’

This note concerns the paper [Janiak A, Kovalyov MY, Lichtenstein M. On a single machine-scheduling problem with separated position and resource effects. Optimization; 2013. doi:10.1080/02331934.2013.804077], which presents an analysis, a counterexample and a pseudocode related with our proof of optimality for a resource allocation algorithm given in [Rudek A, Rudek R. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Comput. Math. Appl. 2011;62:1870–1878]. We show that the discussed analysis is based only on one part of our proof omitting its integral second part, which is the source of misunderstanding. The considered counterexample is applied for an algorithm, which was not the method presented in our paper, whereas our algorithm provides the correct result for the mentioned counterexample. The provided pseudocode of the resource allocation algorithm, which is presented as the correct method, is a pseudocode of the algorithm described in our paper. Therefore, we show that the results presented in our paper are correct.     

置换流水车间调度问题的中心引力优化算法求解

目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。     

含有等式约束非线性规划的全局优化算法

针对含有多个等式约束的非线性规划问题,提出一个全局优化算法.该方法基于可行集策略把改进的模拟退火方法与确定的局部算法方法相结合.对算法的收敛性进行了证明,数值结果表明算法的有效性及正确性.     

Four Payment Models for the Multi-Mode Resource Constrained Project Scheduling Problem with Discounted Cash Flows

In this paper, the multi-mode resource constrained project scheduling problem with discounted cash flows is considered. The objective is the maximization of the net present value of all cash flows. Time value of money is taken into consideration, and cash in- and out-flows are associated with activities and/or events. The resources can be of renewable, nonrenewable, and doubly constrained resource types. Four payment models are considered: lump sum payment at the terminal event, payments at prespecified event nodes, payments at prespecified time points and progress payments. For finding solutions to problems proposed, a genetic algorithm (GA) approach is employed, which uses a special crossover operator that can exploit the multi-component nature of the problem. The models are investigated at the hand of an example problem. Sensitivity analyses are performed over the mark up and the discount rate. A set of 93 problems from literature are solved under the four different payment models and resource type combinations with the GA approach employed resulting in satisfactory computation times. The GA approach is compared with a domain specific heuristic for the lump sum payment case with renewable resources and is shown to outperform it.