Enhancing genetic algorithms for dependent job scheduling in grid computing environments

Genetic Algorithms (GAs) are stochastic search techniques based on principles of natural selection and recombination that attempt to find optimal solutions in polynomial time by manipulating a population of candidate solutions. GAs have been widely used for job scheduling optimisation in both homogeneous and heterogeneous computing environments. When compared with list scheduling heuristics, GAs can potentially provide better solutions but require much longer processing time and significant experimentation to determine GA parameters. This paper presents a GA for scheduling dependent jobs in grid computing environments. A?number of selection and pre-selection criteria for the GA are evaluated with an aim to improve GA performance in job scheduling optimization. A?Task Matching with Data scheme is proposed as a GA mutation operator. Furthermore, the effect of the choice of heuristics for seeding the GA is investigated.     

项目调度中的测试问题集选取研究

为了更好测试和比较项目调度问题求解算法的性能,通常需要利用测试问题集对相关算法进行测试和比较。对现有测试问题集的研究进行综述,并重点介绍国际上常用的两套标准问题集（Patterson问题集和PSPLIB标准问题库）和两款用于生成问题集的软件（单项目调度问题集生成器RanGen和多项目调度问题集生成器RCMPSP）,最后,提出项目调度问题中选取问题集的一般流程以及构建问题集的一般方法,并通过实例说明该问题集选取方法的有效性及应用前景。     

An efficient job scheduling algorithm for mixed turnaround and deadline applications

Computer job scheduling is often performed with little understanding of the formal properties of the jobs being scheduled. One reason for this is that optimal solutions for job scheduling on computers are difficult to obtain if the job stream has mixed objectives, i.e., it consists of some jobs whose turnaround time has to be minimized and others whose deadlines must be met. A practical algorithm for scheduling mixed job streams on monoprogrammed computers, with potential application to a multiprogramming environment, is presented. The algorithm takes into account variable cost rates for each job. Experimental results illustrate the efficiency of the algorithm in terms of both its proximity to optimal solutions and its low computational complexity.     

Data Intensive and Network Aware (DIANA) Grid Scheduling

In Grids scheduling decisions are often made on the basis of jobs being either data or computation intensive: in data intensive situations jobs may be pushed to the data and in computation intensive situations data may be pulled to the jobs. This kind of scheduling, in which there is no consideration of network characteristics, can lead to performance degradation in a Grid environment and may result in large processing queues and job execution delays due to site overloads. In this paper we describe a Data Intensive and Network Aware (DIANA) meta-scheduling approach, which takes into account data, processing power and network characteristics when making scheduling decisions across multiple sites. Through a practical implementation on a Grid testbed, we demonstrate that queue and execution times of data-intensive jobs can be significantly improved when we introduce our proposed DIANA scheduler. The basic scheduling decisions are dictated by a weighting factor for each potential target location which is a calculated function of network characteristics, processing cycles and data location and size. The job scheduler provides a global ranking of the computing resources and then selects an optimal one on the basis of this overall access and execution cost. The DIANA approach considers the Grid as a combination of active network elements and takes network characteristics as a first class criterion in the scheduling decision matrix along with computations and data. The scheduler can then make informed decisions by taking into account the changing state of the network, locality and size of the data and the pool of available processing cycles.     

基于动态规划的资源受限随机工序调度

为解决资源受限条件下的随机工序调度问题,该文提出一种基于离散随机动态系统描述的加工时间离散随机分布且同时具有不兼容和多种可更新资源约束的资源受限项目调度模型,使得在满足资源约束和工序约束的前提下,总的平均加工时间最短。该系统研究了动态规划算法求解该问题的方法。通过实例,验证了该方法的有效性和可行性。     

A global constraint for total weighted completion time for unary resources

We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, we propose an O(n ⁴) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.     

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

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

多技能维修服务干扰管理研究

针对多技能维修工人调度系统的干扰管理问题，以最小化干扰对原调度计划的影响为目标建立了客户需求变化的干扰管理模型。利用前景理论度量多技能工维修调度系统中的三个利益主体客户、服务中心管理人员和多技能维修工人的干扰，同时考虑到多技能工掌握的技能与任务需要的技能的匹配的约束，以及服务时间的约束。利用遗传算法对模型进行求解，验证了干扰管理模型的有效性。     

Project scheduling under resource constraints: Application of the cumulative global constraint in a decision support framework

This paper concerns project scheduling under resource constraints. Traditionally, the objective is to find a unique solution that minimizes the project makespan, while respecting the precedence constraints and the resource constraints. This work focuses on developing a model and a decision support framework for industrial application of the cumulative global constraint. For a given project scheduling, the proposed approach allows the generation of different optimal solutions relative to the alternate availability of outsourcing and resources. The objective is to provide a decision-maker an assistance to construct, choose, and define the appropriate scheduling program taking into account the possible capacity resources. The industrial problem under consideration is modeled as a constraint satisfaction problem (CSP). It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the tasks realized on each resource, as well as the curves with the profile of the total consumption of resources on time.     

复杂产品开发项目调度问题的模糊优化算法

对具有不确定时间参数的复杂产品开发项目调度问题,提出一种有效的模糊优化调度算法-基于预测的模糊BoP项目调度算法.首先,用模糊数表示不确定的时间参数,并构造相应的模糊数运算方法,对适合于确定性调度问题的BoP算法进行扩展,使其能处理模糊性时间参数.其次,修正了BoP算法中子项目调度方法,提高了算法的调度性能,降低了计算复杂度.大量的数值仿真实验表明,与基于启发式规则的调度算法相比,模糊BoP算法更适合于具有不确定时间参数的复杂产品开发项目调度问题.     

A genetic algorithm-based approach to flexible flow-line schedulingwith variable lot sizes

Genetic algorithms (GAs) have been used widely for such combinatorial optimization problems as the traveling salesman problem (TSP), the quadratic assignment problem (QAP), and job shop scheduling. In all of these problems there is usually a well defined representation which GA's use to solve the problem. We present a novel approach for solving two related problems-lot sizing and sequencing-concurrently using GAs. The essence of our approach lies in the concept of using a unified representation for the information about both the lot sizes and the sequence and enabling GAs to evolve the chromosome by replacing primitive genes with good building blocks. In addition, a simulated annealing procedure is incorporated to further improve the performance. We evaluate the performance of applying the above approach to flexible flow line scheduling with variable lot sizes for an actual manufacturing facility, comparing it to such alternative approaches as pair wise exchange improvement, tabu search, and simulated annealing procedures. The results show the efficacy of this approach for flexible flow line scheduling.     

An integrated security-aware job scheduling strategy for large-scale computational grids

All existing fault-tolerance job scheduling algorithms for computational grids were proposed under the assumption that all sites apply the same fault-tolerance strategy. They all ignored that each grid site may have its own fault-tolerance strategy because each site is itself an autonomous domain. In fact, it is very common that there are multiple fault-tolerance strategies adopted at the same time in a large-scale computational grid. Various fault-tolerance strategies may have different hardware and software requirements. For instance, if a grid site employs the job checkpointing mechanism, each computation node must have the following ability. Periodically, the computational node transmits the transient state of the job execution to the server. If a job fails, it will migrate to another computational node and resume from the last stored checkpoint. Therefore, in this paper we propose a genetic algorithm for job scheduling to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. We assume that the system supports four kinds fault-tolerance mechanisms, including the job retry, the job migration without checkpointing, the job migration with checkpointing, and the job replication mechanisms. Because each fault-tolerance mechanism has different requirements for gene encoding, we also propose a new chromosome encoding approach to integrate the four kinds of mechanisms in a chromosome. The risk nature of the grid environment is also taken into account in the algorithm. The risk relationship between jobs and nodes are defined by the security demand and the trust level. Simulation results show that our algorithm has shorter makespan and more excellent efficiencies on improving the job failure rate than the Min–Min and sufferage algorithms.     

Integration of priority dispatching and due-date assignment in a job shop

A simulation study to investigate the effect on missed due-dates and job flow-time is discussed by combining the job dispatching and due-date assignment decisions in job shop scheduling. A ‘semi-local’ due-date-oriented dispatching rule is designed which is able to monitor the progress of jobs closely. The performance of the dispatching rule is enhanced by a rational due-date assignment procedure which takes account of both job content and shop status information in determining due-dates. The simulation results show that the combined scheduling procedure performs better than some common simple dispatching rules which are used with the total-work-content (TWK) due-date assignment method.     

基于Petri网的柔性制造系统无死锁遗传调度算法

对以最小化加工时间为目标的柔性制造系统无死锁调度问题, 提出了一种遗传调度算法. 算法考虑到同类工件具有预先确定的相同加工路径, 而各工序的处理时间与工件有关. 用Petri网对工序和资源分配进行逻辑建模,利用遗传算法, 采用工序自然编码方式, 基于系统的最佳避免死锁Petri网控制器, 检测染色体的可行性, 修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束, 从而保证算法所利用的所有染色体都对应系统的可行调度. 仿真结果表明了算法的可行性和有效性.     

Location-based measurement and visualization for interdependence network on construction sites

Appropriately assigning workers to tasks is vitally important in project management. To do this, project managers need to objectively and effectively measure and visualize the spatiotemporal orders of real construction process as well as coordination structure of the workforce. However, currently there is no method/tool available to project managers to represent spatiotemporal orders of construction processes. To address this issue, this paper presents a novel approach to measuring the real spatiotemporal order of onsite tasks as well as the task interdependence by an interdependence network. This approach extracts the distance of workspace distributions as a key interdependence indicator from historical location tracks across different construction stages according to the area-restricted nature of construction activities. It then integrates generated interdependence into a network over time, to imply the cooperation patterns in stages and a task delivery across stages with a holistic view. To validate the approach, location data were collected from 31 workers working in a high-rise housing construction project for one week to construct the interdependence network of this project, which was used to quantitatively evaluate the performance of construction schedule, assignments and cooperation. Results show that the interdependence network is able to provide insightful information on how workers perform individual tasks onsite and it is also an effective tool to identify and display the interactions among site workers.     

Solving a comprehensive model for multiobjective project portfolio selection

Any organization is routinely faced with the need to make decisions regarding the selection and scheduling of project portfolios from a set of candidate projects. We propose a multiobjective binary programming model that facilitates both obtaining efficient portfolios in line with the set of objectives pursued by the organization, as well as their scheduling regarding the optimum time to launch each project within the portfolio without the need for a priori information on the decision-maker's preferences. Resource constraints, the possibility of transferring resources not consumed in a given a period to the following one, and project interdependence have also been taken into account. Given that the complexity of this problem increases as the number of projects and the number of objectives increase, we solve it using a metaheuristic procedure based on Scatter Search that we call SS-PPS (Scatter Search for Project Portfolio Selection). The characteristics and effectiveness of this method are compared with other heuristic approaches (SPEA and a fully random procedure) using computational experiments on randomly generated instances.

Statement of scope and purpose

This paper describes a model to aid in the selection and scheduling of project portfolios within an organization. The model was designed assuming strong interdependence between projects, which therefore have to be assessed in groups, while allowing individual projects to start at different times depending on resource availability or any other strategic or political requirements, which involves timing issues. The simultaneous combination of project portfolio selection and scheduling under general conditions involves known drawbacks that we attempt to remedy. Finally, the model takes into account multiple objectives without requiring a priori specifications regarding the decision-maker's preferences.The resolution of the problem was approached using a metaheuristic procedure, which showed by computational experiments good performance compared with other heuristics.     

Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.     

柔性工时约束下项目调度及其蚁群算法

针对软件工程项目调度问题,在考虑加班工时的情况下,提出了柔性工时约束下项目调度问题的数学模型,并设计了相应的蚁群算法。模型对项目人力资源的特殊性进行了分析,指出项目人力资源是一种特殊的可更新资源,在允许加班的情况下,人力资源构成特殊的柔性工时约束。针对所设计的数学模型,在并行项目进度生成机制基础上设计了蚁群算法,并通过算例进行验证与分析。     

Taking advantage of solving the resource constrained multi-project scheduling problems using multi-modal genetic algorithms

In this paper, for the first time, multi-modal genetic algorithms (MMGAs) are proposed to optimize the resource constrained multi-project scheduling problem (RCMPSP). In problems where the landscape has both multiple local and global optima, such as the RCMPSP, a MMGAs approach can provide managers with an advantage in decision-making because they can choose between alternative solutions equally good. Alternative optima are achieved because the diversification techniques of MMGAs introduce diversity in population, decreasing the possibility of the optimization process getting caught in a unique local or global optimum. To compare the performance of a MMGAs approach with other alternative approaches, commonly accepted by researchers to solve the RCMPSP such as classical genetic algorithms and dispatching heuristics based on priority rules, we analyse two time-based objective functions (makespan and average percent delay) and three coding systems [random keys (RK), activity list (AL), and a new proposal called priority rule (PR)]. We have found that MMGAs significantly improve the efficacy (the algorithm’s capability to find the best optimum) and the multi-solution-based efficacy (the algorithm’s capability to find multiple optima) of the other two approaches. For makespan the PR is the best code in terms of the efficacy and multi-solution-based efficacy, and the RK is the best code for the average percent delay.     

A GA optimization model for workgroup-based repetitive scheduling (WoRSM)

Most construction repetitive scheduling methods developed so far have been based on the premise that a repetitive project is comprised of many identical production units. Recently Huang and Sun [Huang RY, Sun KS. Non-unit based planning and scheduling of repetitive construction project. J Constr Eng Manage ASCE 2006;132(6):585–97] developed a workgroup-based repetitive scheduling method that takes the view that a repetitive construction project consists of repetitive activities of workgroups. Instead of repetitive production units, workgroups with repetitive or similar activities in a repetitive project are identified and employed in the planning and scheduling. The workgroup-based approach adds more flexibility to the planning and scheduling of repetitive construction projects and enhances the effectiveness of repetitive scheduling. This work builds on previous research and develops an optimization model for workgroup-based repetitive scheduling. A genetic algorithm (GA) is employed in model formation for finding the optimal solution. A chromosome representation, as well as specification of other parameters for GA analysis, is described in the paper. A sample case study is used for model validation and demonstration. Results and findings are reported.