Heuristic framework for the resource constrained multi-project scheduling problem

Real world scheduling problems can be affected by diverse and conflicting goals. Some scheduling problems are bounded with limited resources and represent a considerable challenge to planners. When multiple projects are involved, scheduling problems become even more complex and difficult to resolve. Because of the combinatory explosions and unrealistic assumptions, traditional management sciences techniques such as PERT, CPM, and a host of similar project schedulers are very limited to special cases of scheduling problems. Recent developments of artificial intelligence (AI) and knowledge engineering techniques have made the development of expert systems which can be driven by scheduling heuristics to resolve problems associated with the traditional optimization techniques by giving “better” rather than “best” solutions. This paper presents the conceptual framework and development strategy for an expert system in multi-project scheduling domains. This paper will also present a practical application of the scheduling system.     

Deep reinforcement learning for solving resource constrained project scheduling problems with resource disruptions

The resource-constrained project scheduling problem (RCPSP) is encountered in many fields, including manufacturing, supply chain, and construction. Nowadays, with the rapidly changing external environment and the emergence of new models such as smart manufacturing, it is more and more necessary to study RCPSP considering resource disruptions. A framework based on reinforcement learning (RL) and graph neural network (GNN) is proposed to solve RCPSP and further solve the RCPSP with resource disruptions (RCPSP-RD) on this basis. The scheduling process is formulated as sequential decision-making problems. Based on that, Markov decision process (MDP) models are developed for RL to learn scheduling policies. A GNN-based structure is proposed to extract features from problems and map them to action probability distributions by policy network. To optimize the scheduling policy, proximal policy optimization (PPO) is applied to train the model end-to-end. Computational results on benchmark instances show that the RL-GNN algorithm achieves competitive performance compared with some widely used methods.     

基于BS-GA的资源约束多项目调度问题研究

针对资源约束的多项目调度问题(RCMPSP),考虑到项目、项目任务和资源各自之间的差异性,引入项目权重系数、活动质量因子和资源能力系数3个概念,提出了一个工期与质量的均衡优化模型.该模型根据资源的配置计划,确定了项目任务的资源平均能力系数,然后用项目权重系数和活动质量因子计算出多项目的单位工期时间内资源平均能力系数,利...     

Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach

We consider the multiprocessor scheduling of unit time tasks with precedence constraints and finite set of limited resources. Each task demands some amount of resources for its execution and the total demand for each kind of resources must not exceed a certain limit at any instant of time. Our objective is to find out the minimum time schedule which satisfies the partial orders and the resource usage constraints. We have applied Genetic Algorithm for the present problem. We have shown that the Genetic Algorithm is quite superior to the First Fit Decreasing method.     

Hybrid genetic algorithms for constrained placement problems

When solving real-world problems, often the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infeasible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for 2D combinatorial placement and packing problems. Empirical results are presented for two constrained placement problems, the facility layout problem and the generation of VLSI macro-cell layouts. For multiobjective optimization problems, common approaches often deal with the different objectives in different phases and thus are unable to efficiently solve the global problem. Due to a tree structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step     

Multi-operator based evolutionary algorithms for solving constrained optimization problems

Over the last two decades, many sophisticated evolutionary algorithms have been introduced for solving constrained optimization problems. Due to the variability of characteristics in different COPs, no single algorithm performs consistently over a range of problems. In this paper, for a better coverage of the problem characteristics, we introduce an algorithm framework that uses multiple search operators in each generation. The appropriate mix of the search operators, for any given problem, is determined adaptively. The framework is tested by implementing two different algorithms. The performance of the algorithms is judged by solving 60 test instances taken from two constrained optimization benchmark sets from specialized literature. The first algorithm, which is a multi-operator based genetic algorithm (GA), shows a significant improvement over different versions of GA (each with a single one of these operators). The second algorithm, using differential evolution (DE), also confirms the benefit of the multi-operator algorithm by providing better and consistent solutions. The overall results demonstrated that both GA and DE based algorithms show competitive, if not better, performance as compared to the state of the art algorithms.     

改进差异演化算法求解约束优化问题

在现实生活中许多实际问题都可以转化为约束优化问题,并且实际问题通常都很复杂,其函数形态各具特色,传统基于梯度信息的各种求解策略对于具有不可微、多峰及非凸的非线性函数约束优化问题很难凑效。而最近兴起的智能类算法却对这类问题的求解效果突出,在借鉴国外的差异演化算法研究成果基础上,运用改进差异演化算法来求解约束优化问题。最后通过实例进行仿真实验,结果表明改进差异演化算法在求解约束优化问题时具有一定的优越性。     

Efficient genetic algorithms using discretization scheduling

In many applications of genetic algorithms, there is a tradeoff between speed and accuracy in fitness evaluations when evaluations use numerical methods with varying discretization. In these types of applications, the cost and accuracy vary from discretization errors when implicit or explicit quadrature is used to estimate the function evaluations. This paper examines discretization scheduling, or how to vary the discretization within the genetic algorithm in order to use the least amount of computation time for a solution of a desired quality. The effectiveness of discretization scheduling can be determined by comparing its computation time to the computation time of a GA using a constant discretization. There are three ingredients for the discretization scheduling: population sizing, estimated time for each function evaluation and predicted convergence time analysis. Idealized one- and two-dimensional experiments and an inverse groundwater application illustrate the computational savings to be achieved from using discretization scheduling.     

Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with CUDA

In this paper we propose an improved algorithm to search optimal solutions to the flow shop scheduling problems with fuzzy processing times and fuzzy due dates. A longest common substring method is proposed to combine with the random key method. Numerical simulation shows that longest common substring method combined with rearranging mating method improves the search efficiency of genetic algorithm in this problem. For application in large-sized problems, we also enhance this modified algorithm by CUDA based parallel computation. Numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU. Based on the modified algorithm invoking with CUDA scheme, we can search satisfied solutions to the fuzzy flow shop scheduling problems with high performance.     

Heuristic algorithms for solving earliness-tardiness scheduling problems with machine vacations

The earliness and tardiness (E/T) penalty problem in scheduling gained more importance in part due to its application in Just-In-Time (JIT) production system. Inorder to meet JIT production schedules preventive maintenance plan must be in place. During the maintenance periods machine is not available for processing. The time duration planned for preventive maintenance or meal breaks is called machine vacation. Incorporating E/T penalty and machine vacation a single machine scheduling model is developed. Heuristic methods for solving this problem and computational results are also presented.     

Analysis of distributed genetic algorithms for solving cutting problems

In this paper, a solution to the three‐stage two‐dimensional cutting problem is presented by using sequential and parallel genetic algorithms (GAs). More specifically, an analysis of including distributed population ideas and parallelism in the basic GA are carried out to solve the problem more accurately and efficiently than with ordinary sequential techniques. Publicly available test problems have been used to illustrate the computational performance of the resulting metaheuristics. Experimental evidence in this work will show that the proposed algorithms outperform their sequential counterparts in time (high speedup with multiprocessors) and numerically (lower number of visited points during the search to find the solutions).     

Precast production scheduling using multi-objective genetic algorithms

The goal of production scheduling is to achieve a profitable balance among on-time delivery, short customer lead time, and maximum utilization of resources. However, current practices in precast production scheduling are fairly basic, depending heavily on experience, thereby resulting in inefficient resource utilization and late delivery. Moreover, previous methods ignoring buffer size between stations typically induce unfeasible schedules. Certain computational techniques have been proven effective in scheduling. To enhance precast production scheduling, this research develops a multi-objective precast production scheduling model (MOPPSM). In the model, production resources and buffer size between stations are considered. A multi-objective genetic algorithm is then developed to search for optimum solutions with minimum makespan and tardiness penalties. The performance of the proposed model is validated by using five case studies. The experimental results show that the MOPPSM can successfully search for optimum precast production schedules. Furthermore, considering buffer sizes between stations is crucial for acquiring reasonable and feasible precast production schedules.     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

Multi-level parallel chaotic Jaya optimization algorithms for solving constrained engineering design problems

The Journal of Supercomputing - Several heuristic optimization algorithms have been applied to solve engineering problems. Most of these algorithms are based on populations that evolve according to...     

Two-dimensional packing problems using genetic algorithms

This paper presents a technique for applying genetic algorithms for the two-dimensional packing problem. The approach is applicable to not only convex shaped objects, but can also accommodate any type of concave and complex shaped objects including objects with holes. In this approach, a new concept of a two-dimensional genetic chromosome is introduced. The total layout space is divided into a finite number of cells for mapping it into this 2D genetic algorithm chromosome. The mutation and crossover operators have been modified and are applied in conjunction with connectivity analysis for the objects to reduce the creation of faulty generations. A new feature has been added to the Genetic Algorithm (GA) in the form of a new operator called compaction. Several examples of GA-based layout are presented.     

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

Multi-criteria sequence-dependent job shop scheduling using genetic algorithms

Real world job shops have to contend with jobs due on different days, material ready times that vary, reentrant workflows and sequence-dependent setup times. The problem is even more complex because businesses often judge solution goodness according to multiple competing criteria. Producing an optimal solution would be time consuming to the point of rendering the result meaningless. Commonly used heuristics such as shortest processing time (SPT) and earliest due date (EDD) can be used to calculate a feasible schedule quickly, but usually do not produce schedules that are close to optimal in these job shop environments. We demonstrate that genetic algorithms (GA) can be used to produce solutions in times comparable to common heuristics but closer to optimal. Changing criteria or their relative weights does not affect the running time, nor does it require programming changes. Therefore, a GA can be easily applied and modified for a variety of production optimization criteria in a job shop environment that includes sequence-dependent setup times.     

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.     

求解工程约束问题的新型智能优化算法及展望

为了研究新型智能优化算法的性能和应用前景,选择了近几年提出的6种仿生智能优化算法:哈里斯鹰优化(HHO)算法、平衡优化(EO)算法、海洋捕食者算法(MPA)、政治优化(PO)算法、黏液霉菌算法(SMA)和堆阵优化(HBO)算法,对其性能和在不同带约束的工程优化问题上的应用进行对比分析.首先,对6种优化算法的基本原理进行...