Resource-constrained flowshop scheduling with separate resource recycling operations

This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem.     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

资源约束项目调度研究综述

资源约束项目调度问题(RCPSP)研究资源的合理利用和项目活动的合理调度,实现既定目标的最优化,具有很强的工程背景,近年来得到了学术界和工业界的广泛关注.为此,介绍了RCPSP的数学模型以及多种问题的扩充,总结了相关理论,重点综述了RCPSP的算法,并归纳了若干应用进展.最后指出了有待进一步研究的方向和内容.     

Solving resource-constrained project scheduling problems: Conceptual validation of FLP formulation and efficient permutation-based ABC computation

In this paper, we propose two alternative approaches, applying the facility layout problem (FLP) concept and integrating the permutation-based artificial bee colony (PABC) algorithm, to effectively tackle the resource-constrained project scheduling problem (RCPSP). In the FLP formulation, the constraints are expressed to design the activities in the space constructed by resource and temporal restrictions, without violating the precedence relationships and overlaps between the activities. For dodging the difficulty of the FLP-based model to treat large-sized instances of NP-hard RCPSP, the permutation representation scheme of the PABC algorithm is in turn introduced utilizing the artificial bee colony (ABC) process to search the best solution for RCPSP. In the procedure, a crossover operator and an insert operator following the update equation of the ABC algorithm are devised to augment the effectiveness of computation, whereas a shift operator subject to the resource utilization ratio value is suggested to diversify the solutions. The makespan is then obtained and improved with the assistance of a serial scheduling scheme and a double justification skill. Subsequently, the computational experiments conducted substantiate the conceptual validity of the proposed facility layout formulation for RCPSP and the comprehensive simulation shows the effectiveness of the PABC algorithm for RCPSP.     

Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting

In this paper, we explore the difference between preemption and activity splitting in the resource-constrained project scheduling problem (RCPSP) literature and identify a new set of RCPSPs that only allows non-preemptive activity splitting. Each activity can be processed in multiple modes and both renewable and non-renewable resources are considered. Renewable resources have time-varying resource constraints and vacations. Multi-mode RCPSP (MRCPSP) with non-preemptive activity splitting is shown to be a generalization of the RCPSP with calendarization. Activity ready times and due dates are considered to study the impact on project makespan. Computational experiments are conducted to compare optimal makespans under three different problem settings: RCPSPs without activity splitting (P1), RCPSPs with non-preemptive activity splitting (P2), and preemptive RCPSPs (P3). A precedence tree-based branch-and-bound algorithm is modified as an exact method to find optimal solutions. Resource constraints are included into the general time window rule and priority rule-based simple heuristics are proposed to search for good initial solutions to tighten bounding rules. Results indicate that there are significant makespan reductions possible when non-preemptive activity splitting or preemptions are allowed. The higher the range of time-varying renewable resource limits and the tighter the renewable resource limits are, the bigger the resulting makespan reduction can be.     

资源约束项目的改进差分进化参数控制及双向调度算法

针对资源约束项目调度组合优化难题, 提出一种改进的动态差分进化参数控制及双向调度算法.通过参数时变衰减与个体优劣评价, 自适应控制个体进化参数, 提高算法的收敛性能、勘探与开发最优解的能力; 基于动态差分进化(Dynamic differential evolution, DDE), 提出一种双向调度算法, 使用满足任务时序约束的优先数编码、交替正向反向调度, 结合标准化编码调整与精英保留的种群随机重建策略, 建立了一种高效稳健的双向编码调整机制.通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试, 并与其他文献算法比较最优解平均偏差率, 验证了所提算法的有效性与优越性.     

基于混合遗传算法的资源受限的运输任务调度

在利用串行调度启发式方法解决资源受限的运输任务调度问题（RCTTSP）的基础之上,提出了一种混合遗传算法（HGA）。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。     

Multi-objective scheduling with fuzzy due-date

In this paper, we examine the characteristic features of multi-objective scheduling problems formulated with the concept of fuzzy due-date. By computer simulations, we show that various scheduling criteria can be expressed by modifying the shape of membership functions of fuzzy due-dates. We also show the difficulty in handling the minimum satisfaction grade as a scheduling criterion. This difficulty is caused by the fact that the minimum satisfaction grade is zero for almost all schedules. This makes many search algorithms inefficient. We suggest an idea to cope with this difficulty.     

粒子群算法求解任务可拆分项目调度问题

首先针对任务可拆分的项目调度问题,提出一种带有局部搜索的粒子群算法LSPSO;然后采用基于任务排列的粒子表示方法,将遗传算法中的定位交叉引入粒子的更新过程中,并采用局部搜索技术对更新后的粒子进行改进;最后对Patterson测试集中110个问题实例进行了测试,实验结果表明,算法LSPSO具有较快的速度,所给出的调度方案较优.     

Project scheduling under partially renewable resources and resource consumption during setup operations

There has been an increasing pressure on manufacturing industries to reduce energy consumption. In this study, we propose a new variant of RCPSP called RCPSP/πRC, which can deal with realistic energy constraints such as power restriction during peak hours, contract demand, and energy consumption during setup operations. First, we present an integer programming (IP) model and a constraint programming (CP) model of the RCPSP/πRC. Next, we present a heuristic mode restriction method called a mask calculation algorithm to achieve efficient searching by restricting selectable modes. Finally, through computational experiments, we evaluate the proposed methods and show their effectiveness.     

Augmenting priority rule heuristics with justification and rollout to solve the resource-constrained project scheduling problem

The key question addressed by the resource-constrained project scheduling problem (RCPSP) is to determine the start times for each activity such that precedence and resource constraints are satisfied while achieving some objective. Priority rule-based heuristics are widely used for large problems. Rollout and justification can be integrated with priority rule heuristics to solve the RCPSP. We develop several such procedures and examine the resulting solution quality and computational cost. We present empirical evidence that these procedures are competitive with the best solution procedures described in the literature.     

Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems

Project scheduling is an inherently multi-objective problem, since managers want to finish projects as soon as possible with the minimum cost and the maximum quality. However, there are only a few papers dealing with multiobjective resource-constrained project scheduling problems (MORCPSPs). Moreover, there is no theoretical study in the literature that establishes the fundamentals for correct algorithmic developments. In this paper we try to close the gap by proving several results for MORCPSPs. With these results as a basis, both exact and heuristic procedures capable of obtaining a set of efficient solutions for several important MORCPSPs can be created.     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.     

A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling

This paper presents an effective heuristic algorithm based on the framework of the filter-and-fan (F&F) procedure for solving the resource-constrained project scheduling problem (RCPSP). The proposed solution methodology, called the filter-and-fan approach with adaptive neighborhood switching (FFANS), operates on four different neighborhood structures and incorporates improved local search, F&F search with multiple neighborhoods and an adaptive neighborhood switching procedure. The improved local search, in which a new insert-based move strategy and new time compression measurement of schedules having the same makespan are embedded, is utilized to identify a local optimum and a basic move list. The F&F search, aimed to further improve the local optimum, applies multi-neighborhood filter and fan strategies to generate compound moves and a neighborhood-switch list in a tree search fashion. When the current neighborhood cannot further improve the local optimum, the adaptive neighborhood switching procedure picks the most potential neighborhood for the next run of the local search procedure. The entire solution procedure is autonomous and adaptive due to its variable search range depending on the project sizes and characteristics. Computational results and comparisons with some state-of-the-art algorithms indicate the effectiveness and competence of the proposed FFANS.     

Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming

This contribution presents a novel approach to address the scheduling of resource-constrained flexible manufacturing systems (FMSs). It deals with several critical features that are present in many FMS environments in an integrated way. The proposal consists in a constraint programming (CP) formulation that simultaneously takes into account the following sub-problems: (i) machine loading, (ii) manufacturing activities scheduling, (iii) part routing, (iv) machine buffer scheduling, (v) tool planning and allocation, and (vi) AGV scheduling, considering both the loaded and the empty movements of the device. Before introducing the model, this work points out the problems that might appear when all these issues are not concurrently taken into account. Then, the FMS scheduling model is presented and later assessed through several case-studies. The proposed CP approach has been tested by resorting to problems that consider dissimilar number of parts, operations per part, and tool copies, as well as different AGV speeds. The various examples demonstrate the importance of having an integrated formulation and show the important errors that can occur when critical issues such as AGV empty movements are neglected.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling

Traditionally, the resource-constrained project scheduling problem (RCPSP) is modeled as a static and deterministic problem and is solved with the objective of makespan minimization. However, many uncertainties, such as unpredictable increases in processing times caused by rework or supplier delays, random transportation and/or setup, may render the proposed solution obsolete. In this paper, we present a two-stage algorithm for robust resource-constrained project scheduling. The first stage of the algorithm solves the RCPSP for minimizing the makespan only using a priority-rule-based heuristic, namely an enhanced multi-pass random-biased serial schedule generation scheme. The problem is then similarly solved for maximizing the schedule robustness while considering the makespan obtained in the first stage as an acceptance threshold. Selection of the best schedule in this phase is based on one out of 12 alternative robustness predictive indicators formulated for the maximization purpose. Extensive simulation testing of the generated schedules provides strong evidence of the benefits of considering robustness of the schedules in addition to their makespans. For illustration purposes, for 10 problems from the well-known standard set J30, both robust and non-robust schedules are executed with a 10% duration increase that is applied to the same randomly picked 20% of the project activities. Over 1000 iterations per instance problem, the robust schedules display a shorter makespan in 55% of the times while the non-robust schedules are shown to be the best performing ones in only 6% of the times.     

Minimising mean tardiness with alternative operations in two-machine flow-shop scheduling

This paper describes the development of a mixed binary integer programming (BIP) model for scheduling alternative operations in two-machine flow-shop problems with mean tardiness as the criterion. Although the mixed BIP model provides an optimal solution, its variables and constraints increase drastically as the number of jobs increases. Therefore, an optimal solution is not always attainable within the allowable time by solving the mixed BIP model. Consequently, two heuristics suitable for the formulated scheduling problems are proposed. Computational experiments are conducted to test the accuracy and efficiency of the heuristics in generating near optimal solutions for minimising the mean tardiness of jobs.     

Two-machine flowshop scheduling with conditional deteriorating second operations

This paper considers a flowshop‐scheduling problem with a waiting time constraint imposed to restrict the processing of the two operations of each job. If the second operation of a job cannot start within a specified waiting time after the completion of its first operation, then an extra processing time will be incurred for its second operation as a penalty. We first show that even a greatly restricted version of the problem is strongly ????‐hard. We then develop an O(n²) algorithm to determine the makespan of a processing sequence of the jobs.     

Event-based MILP models for resource-constrained project scheduling problems

In this paper we make a comparative study of several mixed integer linear programming (MILP) formulations for resource-constrained project scheduling problems (RCPSPs).