Priority-based heuristics for the multi-skill resource constrained project scheduling problem

In this paper we investigate one of the most recent extensions of the Resource Constrained Project Scheduling Problem (RCPSP): the Multi-Skill Resource Constrained Project Scheduling Problem (MSRCPSP). For this complex problem we propose the use of a parallel scheduling scheme. Such scheme has been successfully applied to the RCPSP. Nevertheless, in order to apply it to the MSRCPSP two new concepts are developed: resource weight and activity grouping. We discuss such concepts and use them for the new heuristic framework proposed. A series of computational tests performed using a large number of instances and reported in this paper shows that the new heuristic is very effective in finding high quality solutions within very small CPU times.     

基于模糊理论的软件项目调度算法

针对软件项目调度问题中信息的不确定性及资源分配的特殊性需要,提出了一种基于模糊理论的软件项目调度算法FSSA。该算法采用模糊数表示任务的工期并应用遗传算法产生任务的调度序列。实验结果表明,FSSA算法能在很短的时间内得到理想的结果,有一定的应用价值。     

多资源约束的项目调度问题离散粒子群算法

提出了一种求解多资源约束项目调度问题的离散粒子群算法。调度方案采用了优先权整数编码方法,使用稀疏存储邻接矩阵判定先后约束,使用活动单位时间推迟策略来满足资源约束。算法的创新点在于直接使用了整数编码的调度方案参与迭代计算,并依据计算结果提供的信息做出位置交换。不但解决了处理离散整数编码粒子的难题,而且容易实现,亦可推广至类似整数编码优化问题。测试用例计算结果表明了算法的可行性和有效性。     

Multi-mode resource constrained project scheduling and contractor selection: Mathematical formulation and metaheuristic algorithms

Contractor selection is a matter of particular attraction for project managers whose aim is to complete projects considering time, cost and quality issues. Traditionally, project scheduling and contractor selection decisions are made separately and sequentially. However, it is usually necessary to satisfy some principles and obligations that impose hard constraints to the problem under consideration. Ignoring this important issue and making project scheduling and contractor selection decisions consecutively may be suboptimal to a holistic view that makes all interrelated decisions in an integrated manner. In this paper, an integrated bi-objective optimization model is proposed to deal with Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) and Contractor Selection (CS) problem, simultaneously. The objective of the proposed model is to minimize the total costs of the project, and minimize the makespan of the project, simultaneously. To solve the integrated MRCPSP-CS, two multi-objective meta-heuristic algorithms, Non-Dominated Sorting Genetic Algorithm (NSGA-II) and Multi-Objective Particle Swarm Optimization algorithm (MOPSO), are adopted, and 30 test problems of different sizes are solved. The parameter tuning is performed using the Taguchi method. Then, diversification metric (DM), mean ideal distance (MID), quality metric (QM) and number of Pareto solutions (NPS) are used to quantify the performance of meta-heuristic algorithms. Analytic Hierarchy Process (AHP), as a prominent multi-attribute decision-making method, is used to determine the relative importance of performance metrics. Computational results show the superior performance of MOPSO compared to NSGA-II for small-, medium- and large-sized test problems. Moreover, a sensitivity analysis shows that by increasing the number of available contractors, not only the makespan of the project is shortened, but also, the value of NPS in the Pareto front increases, which means that the decision maker(s) can make a wider variety of decisions in a more flexible manner.     

自适应混合蚁群算法在MRCPSP中的应用

以多模式资源受限项目调度问题（Multi-mode Resource Constrained Project Scheduling Problem, MRCPSP）为背景,针对蚁群算法收敛速度和解的多样性之间的平衡问题,提出一种改进的自适应混合蚁群算法。该算法中参数的取值范围和变化幅度能够随算法的运行同步自适应调整,蚂蚁在取值区间内随机取参形成混合蚁群;在算法中引入先驱侦查蚁、带有排名因子的精英蚁群奖励机制和信息素上下限以优化信息素的更新策略。同时,对于MRCPSP问题中的工期不确定问题,基于模糊理论,利用该算法解出项目工期的估计值和模糊区间加以解决。最后,仿真结果表明,该算法与其他启发式项目调度优化算法相比,能够提高收敛速度和解的质量,较好地解决MRCPSP问题,因此有着较高的实际应用价值。     

Integrated Fuzzy–HMH for project uncertainties in time–cost tradeoff problem

Time–cost tradeoff (TCT) problem in project scheduling studies how to schedule project activities to achieve a tradeoff between project cost and project completion time. It gives project planners both challenges and opportunities to work out the best plan that optimizes time and cost to complete a project. In this paper, we present a novel method which examines the effects of project uncertainties on both, the duration as well as the cost of the activities. This method integrates a fuzzy logic framework with Hybrid Meta-Heuristic. Hybrid Meta-Heuristic (HMH) is an innovative approach which hybridizes a multiobjective genetic algorithm and simulated annealing. Integration of HMH and fuzzy logic is referred to as ‘integrated Fuzzy–HMH’. A rule based fuzzy logic framework brings up changes in the duration and the cost of each activity for the input uncertainties and HMH searches for Pareto-optimal front (TCT profile) for a given set of time–cost pair of each project activity. Two standard test problems from the literature are attempted using HMH. A case study of TCT problem is solved using integrated Fuzzy–HMH. The method solves time–cost tradeoff problems within an uncertain environment and carries out its sensitivity analysis.     

Healthcare service configuration based on project scheduling

Configuration has been recognized as an effective methodology to provide high product variety that caters to individual customer’s needs in the manufacturing industry. For healthcare service configuration, this decision-making process can be taken as service package creation and treated analogously as a project, which is defined as a collection of tasks. This research develops a decision support model to integrate individual patients into the healthcare service configuration process. The healthcare service configuration is formulated as a Resource Constrained Project Scheduling Problem (RCPSP), and a bi-level optimization algorithm based on Genetic Algorithm (GA) is developed for problem solving. The methodology and algorithm are implemented with a case study based on the data obtained from a general hospital in Singapore, which has demonstrated the applicability of healthcare service configuration.     

Preference ratio-based maximum operator approximation and its application in fuzzy flow shop scheduling

Maximum operator distorts the shape(s) of Triangular Fuzzy Numbers (TFNs) and Trapezoidal Fuzzy Numbers (TrFNs) in many problems such as Flow shop scheduling, job-shop scheduling and project scheduling. In this paper, we introduce an appropriate approximation for the maximum operator, in which the weak-dominance fuzzy numbers are ranked based on the concept of preference ratio. Since in most practical cases the due dates and the processing time of scheduling are not deterministic, we consider the scheduling problems with fuzzy processing time. Finally we develop a novel fuzzy CDS algorithm in fuzzy flow shop scheduling by applying the preference ratio concept through an example.     

Enhanced exchange heuristic based resource constrained scheduler using ARTMAP

The Exchange Heuristic (EH) has demonstrated superior results compared with other RCS methods in solving Resource Constrained Scheduling (RCS) problems. Selecting the most promising target constitutes the success of EH. The current version of EH highly depends on experts' intuition in selecting a target. Expert systems and Fuzzy rulebase as well as Neural Network (NN) have been considered as alternatives for human experts. Expert systems are brittle in its nature, and Fuzzy rulebase needs membership functions defined for each linguistic variable. However, these membership function can not be justified and can be very subjective. Therefore, Neural Network is employed because of its capability of learning as well as dealing with fuzzy data. Known examples are used to train the NN. Back propagation algorithm is used first, then Adaptive Resonance Theory (ART) network is employed to reduce training time since new rules come up often. Even at the end of the training the NN, we may end up with local optima or the NN which is too general to specific problems. Utilizing Genetic Algorithm (GA) will help to further refine or adapt the weights of the NN which optimizes target selection strategy for a specific problem.     

A preemptive bound for the Resource Constrained Project Scheduling Problem

The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging ${\mathcal {NP}}$ -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.     

A Modified Genetic Algorithm for solving uncertain Constrained Solid Travelling Salesman Problems

In this paper, a Modified Genetic Algorithm (MGA) is developed to solve Constrained Solid Travelling Salesman Problems (CSTSPs) in crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random environments. In the proposed MGA, for the first time, a new ‘probabilistic selection’ technique and a ‘comparison crossover’ are used along with conventional random mutation. A Solid Travelling Salesman Problem (STSP) is a Travelling Salesman Problem (TSP) in which, at each station, there are a number of conveyances available to travel to another station. Thus STSP is a generalization of classical TSP and CSTSP is a STSP with constraints. In CSTSP, along each route, there may be some risk/discomfort in reaching the destination and the salesman desires to have the total risk/discomfort for the entire tour less than a desired value. Here we model the CSTSP with traveling costs and route risk/discomfort factors as crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random in nature. A number of benchmark problems from standard data set, TSPLIB are tested against the existing Genetic Algorithm (with Roulette Wheel Selection (RWS), cyclic crossover and random mutation) and the proposed algorithm and hence the efficiency of the new algorithm is established. In this paper, CSTSPs are illustrated numerically by some empirical data using this algorithm. In each environment, some sensitivity studies due to different risk/discomfort factors and other system parameters are presented.     

Modified Cuckoo Optimization Algorithm (MCOA) to solve Precedence Constrained Sequencing Problem (PCSP)

In recent years, new meta-heuristic algorithms have been developed to solve optimization problems. Recently-introduced Cuckoo Optimization Algorithm (COA) has proven its excellent performance to solve different optimization problems. Precedence Constrained Sequencing Problem (PCSP) is related to locating the optimal sequence with the shortest traveling time among all feasible sequences. The problem is motivated by applications in networks, scheduling, project management, logistics, assembly flow and routing. Regarding numerous practical applications of PCSP, it can be asserted that PCSP is a useful tool for a variety of industrial planning and scheduling problems. However it can also be seen that the most approaches may not solve various types of PCSPs and in related papers considering definite conditions, a model is determined and solved. In this paper a new approach is presented for solving various types of PCSPs based on COA. Since COA at first was introduced to solve continuous optimization problems, in order to demonstrate the application of COA to find the optimal sequence of the PCSP, some proposed schemes have been applied in this paper with modifications in operators of the basic COA. In fact due to the discrete nature and characteristics of the PCSP, the basic COA should be modified to solve PSCPs. To evaluate the performance of the proposed algorithm, at first, an applied single machine scheduling problem from the literature that can be formulated as a PCSP and has optimal solution is described and solved. Then, several PCSP instances with different sizes from the literature that do not have optimal solutions are solved and results are compared to the algorithms of the literature. Computational results show that the proposed algorithm has better performance compared to presented well-known meta-heuristic algorithms presented to solve various types of PCSPs so far.     

EFM: evolutionary fuzzy model for dynamic activities recognition using a smartphone accelerometer

Activity recognition is an emerging field of research that enables a large number of human-centric applications in the u-healthcare domain. Currently, there are major challenges facing this field, including creating devices that are unobtrusive and handling uncertainties associated with dynamic activities. In this paper, we propose a novel Evolutionary Fuzzy Model (EFM) to measure the uncertainties associated with dynamic activities and relax the domain knowledge constraints which are imposed by domain experts during the development of fuzzy systems. Based on the time and frequency domain features, we define the fuzzy sets and estimate the natural grouping of data through expectation maximization of the likelihoods. A Genetic Algorithm (GA) is investigated and designed to determine the optimal fuzzy rules. To evaluate the EFM, we performed experiments on seven daily life activities of ten human subjects. Our experiments show significant improvement of 9 % in class-accuracy and 11 % in the F-measures of recognized activities compared to existing counterparts. The practical solution to dynamic activity recognition problems is expected to be an EFM, due to EFM’s utilization of smartphones and natural way of handling uncertainties.     

Real-world production scheduling for the food industry: An integrated approach

The present paper offers an integrated approach to real-world production scheduling for the food processing industries. A manufacturing execution system is very appropriate to monitor and control the activities on the shop floor. Therefore, a specialized scheduler, which is the focus of this paper, has been developed to run at the core of such a system. The scheduler builds on the very general Resource Constrained Project Scheduling Problem with Generalized Precedence Relations. Each local decision step (e.g. choosing a route in the plant layout) is modeled as a separate module interconnected in a feedback loop. The quality of the generated schedules will guide the overall search process to continuously improve the decisions at an intermediate level by using local search strategies. Besides optimization methods, data mining techniques are applied to historical data in order to feed the scheduling process with realistic background knowledge on key performance indicators, such as processing times, setup times, breakdowns, etc. The approach leads to substantial speed and quality improvements of the scheduling process compared to the manual practice common in production companies. Moreover, our modular approach allows for further extending or improving modules separately, without interfering with other modules.     

Cost-based Filtering for Shorter Path Constraints

Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.     

Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm

There are various scheduling problems with resource limitations and constraints in the literature that can be modeled as variations of the Resource Constrained Project Scheduling Problem (RCPSP). This paper proposes a new solution representation and an evolutionary algorithm for solving the RCPSP. The representation scheme is based on an ordered list of events, that are sets of activities that start (or finish) at the same time. The proposed solution methodology, namely SAILS, operates on the event list and relies on a scatter search framework. The latter incorporates an Adaptive Iterated Local Search (AILS), as an improvement method, and integrates an event-list based solution combination method. AILS utilizes new enriched neighborhoods, guides the search via a long term memory and applies an efficient perturbation strategy. Computational results on benchmark instances of the literature indicate that both AILS and SAILS produce consistently high quality solutions, while the best results are derived for most problem data sets.     

Fuzzy preference-based multi-objective optimization method

Multiobjective evolutionary computation is still quite young and there are many open research problems. This paper is an attempt to design a hybridized Multiobjective Evolutionary Optimization Algorithm with fuzzy logic called Fuzzy Preference-Based Multi–Objective Optimization Method (FPMOM). FPMOM as an integrated components of Multiobjective Optimization Technique, Evolutionary Algorithm and Fuzzy Inference System able to search and filter the pareto-optimal and provide a good trade-off solution for the multiobjective problem using fuzzy inference method to choose the user intuitive based specific trade-off requirement. This paper will provide a new insight into the behaviourism of interactive Multiobjective Evolutionary Algorithm optimization problems using fuzzy inference method.     

模糊寻优问题的模糊遗传算法FGA

针对模糊寻优问题，本文基于模糊集的质心概念来确定模糊集的大小，并进而提出了模糊遗传算法ＦＧＡ。算法ＦＧＡ与遗传算法ＧＡ有本制区别，能用效地找到了模糊寻优问题的近似解，本文对算法ＦＧＡ的有效性作了较深入的分析。     

Combinatorial auction under fuzzy environment

Combinatorial auction (CA) mechanism allows bundling of multiple items in packages, which can be solved through a clearing method termed as the winner determination problem (WDP). However, to date, there has yet to be a CA model that accounts for the fuzziness of bidders’ submitted prices. The imprecision in submitted prices is the result of the time gap between bid placement and winning bid announcement, which reflects the bidders’ expected values of the goods at the point of contract sale. Despite this common understanding, conventional CA modeling still treats the prices as deterministic. This causes a major shortcoming when an uncertain environment is assumed to be deterministic and solved through conventional WDP. This study shows that a fuzzy environment modeled via a deterministic WDP approach provides overly optimistic revenue for the auctioneer. A method of using possibilistic distributions of submitted prices to account for price uncertainty is proposed and formalized as Fuzzy Combinatorial Auction Winner Determination Problem (Fuzzy CA WDP). The difference in optimal solutions in deterministic WDP and fuzzy WDP reflects the amount of over estimation when a fuzzy situation is treated as though it is precise. It also reflects the information value when the uncertainty inherent in the fuzzy environment is resolved. Given that the information value is quantified in unit dollars, the fuzzy WDP approach allows the auctioneer to estimate its “true” revenue despite price uncertainties.     

多次抢占项目调度问题的混合遗传算法

研究多次抢占式资源受限的项目调度问题，假设任意时间点可作为资源抢占节点且抢占次数不受限制，建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷，在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数，并以标准算例集（Project Scheduling Problem Library，PSPLIB）对算法进行可行性检验。实验结果表明，资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期，设计的算法对问题求解效果良好。