Comparison of multi-objective evolutionary approaches for task scheduling in distributed computing systems

Parallel and distributed systems play an important part in the improvement of high performance computing. In these type of systems task scheduling is a key issue in achieving high performance of the system. In general, task scheduling problems have been shown to be NP-hard. As deterministic techniques consume much time in solving the problem, several heuristic methods are attempted in obtaining optimal solutions. This paper presents an application of Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) and a Non-dominated Sorting Particle Swarm Optimization Algorithm (NSPSO) to schedule independent tasks in a distributed system comprising of heterogeneous processors. The problem is formulated as a multi-objective optimization problem, aiming to obtain schedules achieving minimum makespan and flowtime. The applied algorithms generate Pareto set of global optimal solutions for the considered multi-objective scheduling problem. The algorithms are validated against a set of benchmark instances and the performance of the algorithms evaluated using standard metrics. Experimental results and performance measures infer that NSGA-II produces quality schedules compared to NSPSO.     

云环境下老化感知的任务调度和运行管理框架

研究了云计算系统现有任务调度和运行管理机制,指出在云计算环境下,基础性支撑软件虚拟机和虚拟机管理器在长期运行过程中均会表现出老化现象,从而降低了其性能,进而影响了任务的调度和执行效果。在一定程度上影响了服务质量(QoS)。针对这种情况,提出了一种老化感知的任务调度和运行管理框架,该框架能在任务调度和运行时感知底层虚拟机和虚拟机管理器的老化状况,并通过及时再生手段恢复虚拟机性能,从而降低老化所带来的负面影响,提升系统可用性。基于CloudSim仿真工具,在该框架下实现了Max-Min调度算法,并对比说明了该框架的有效性。     

A hybrid Tabu sample-sort simulated annealing approach for solving distributed scheduling problem

The distributed scheduling problem has been considered as the allocation of a task to various machines in such a way that these machines are situated in different factories and these factories are geographically distributed. Therefore distributed scheduling has fulfilled various objectives, such as allocation of task to the factories and machines in such a manner that it can utilise the maximum resources. The objective of this paper is to minimise the makespan in each factory by considering the transportation time between the factories. In this paper, to address such a problem of scheduling in distributed manufacturing environment, a novel algorithm has been developed. The proposed algorithm gleans the ideas both from Tabu search and sample sort simulated annealing. A new algorithm known as hybrid Tabu sample-sort simulated annealing (HTSSA) has been developed and it has been tested on the numerical example. To reveal the supremacy of the proposed algorithm over simple SSA and Tabu search, more computational experiments have also been performed on 10 randomly generated datasets.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems

Multi-factory production networks have increased in recent years. With the factories located in different geographic areas, companies can benefit from various advantages, such as closeness to their customers, and can respond faster to market changes. Products (jobs) in the network can usually be produced in more than one factory. However, each factory has its operations efficiency, capacity, and utilization level. Allocation of jobs inappropriately in a factory will produce high cost, long lead time, overloading or idling resources, etc. This makes distributed scheduling more complicated than classical production scheduling problems because it has to determine how to allocate the jobs into suitable factories, and simultaneously determine the production scheduling in each factory as well. The problem is even more complicated when alternative production routing is allowed in the factories. This paper proposed a genetic algorithm with dominant genes to deal with distributed scheduling problems, especially in a flexible manufacturing system (FMS) environment. The idea of dominant genes is to identify and record the critical genes in the chromosome and to enhance the performance of genetic search. To testify and benchmark the optimization reliability, the proposed algorithm has been compared with other approaches on several distributed scheduling problems. These comparisons demonstrate the importance of distributed scheduling and indicate the optimization reliability of the proposed algorithm.     

An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem

In this article, an effective hybrid immune algorithm (HIA) is presented to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, a decoding method is proposed to transfer a job permutation sequence to a feasible schedule considering both factory dispatching and job sequencing. Secondly, a local search with four search operators is presented based on the characteristics of the problem. Thirdly, a special crossover operator is designed for the DPFSP, and mutation and vaccination operators are also applied within the framework of the HIA to perform an immune search. The influence of parameter setting on the HIA is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on 420 small-sized instances and 720 large-sized instances are provided. The effectiveness of the HIA is demonstrated by comparison with some existing heuristic algorithms and the variable neighbourhood descent methods. New best known solutions are obtained by the HIA for 17 out of 420 small-sized instances and 585 out of 720 large-sized instances.     

分布式实时系统任务调度算法的设计和实现

针对分布式实时任务中容易引起的任务分配不合理及系统负载不平衡的情况,根据分布式实时任务多机执行的特点及分布式实时系统在同一结点上有多任务执行,提出了两级分布式系统结构下实时任务的调度策略：任务分配和任务调度。实验表明,在任务分配阶段提出的算法可以更合理地平衡任务,在任务调度阶段采用的调度算法能够更好地完成任务的执行。     

Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times

This paper addresses the scheduling problems in a hybrid flowshop with two objectives of minimising the makespan and total tardiness. Since this problem is NP-hard, evolutionary algorithms based on the genetic algorithm (GA) namely; BOGAW, BOGAC, BOGAT, and BOGAS are proposed for searching the Pareto-optimal frontier. In these algorithms, we propose to generate a section of solutions for the next generation using a neighbourhood search structure on the best individual in each generation. The selection procedure selects the best chromosome based on an evaluation mechanism used in the algorithm (i.e., weighted sum, crowding distance, TOPSIS and single-objective). The aim of this paper is to clarify that the cited characteristic is efficient and it enhances the efficiency of algorithms. Therefore, we perform a comparison between the proposed algorithms to find the best alternative. Data envelopment analysis is used to evaluate the performance of approximation methods. The obtained result from the comparison shows that, BOGAC is the more efficient. To continue, since the efficiency of our idea is not clear, we compare our efficient algorithm with other efficient algorithms in the literature (namely PGA-ALS and MOGLS). The final persuasive results support the idea that BOGAC in comparison with PGA-ALS and MOGLS is more effective and efficient.     

An efficient task scheduling algorithm for heterogeneous multi-core processors

针对现有异构多核处理器任务调度算法效率低的问题,提出了一种综合性的、高效的静态任务调度算法,即聚簇与复制列表优化调度(CDLOS)算法.该算法首先通过对任务图进行聚簇优化,降低某些特殊任务的通信开销;然后从整个任务图的拓扑结构出发计算任务的优先级权值,提高关键任务的优先级;继而采用区间插入和任务复制技术进行调度,降低处理器资源浪费;最后通过优化调度结果,消除冗余任务,减小整个任务的调度长度.实例分析和模拟实验结果表明:与以往算法相比,此新算法较高地提升了多核处理器任务调度的效率,具有更好的应用前景.     

Comparison of scheduling algorithms for multifunction radar

The management of radar resources in a multifunction radar is central to unlocking the potential offered by electronic scanning. Scheduling is an important sub-problem of radar resource management because of the strong correlation between how tasks should be performed, as well as the time available to carry them out and their timeliness. Two scheduling algorithms previously reported in the literature are compared in order to investigate differences in their performance. This provides new insights which may be invaluable in the development of future optimal schedulers. A detailed model of a multifunction radar has been developed to enable comparison using the same operational conditions. The radar is assumed to operate in both 'underload' and 'overload' situations. When not fully loaded (i.e. underload), the two scheduling algorithms perform in significantly different ways. However, in the more important case of overload situations, where there are insufficient radar resources to carry out all necessary tasks, both algorithms provide similar performance. Nevertheless, there still remain differences that require careful understanding when selecting the most appropriate scheduler.     

Embedded instrumentation for evaluating task sharing performance ina distributed computing system

An example of application-level performance measurement on a distributed computing system using software-based instrumentation is considered. Embedded software instrumentation for measuring the performance of a decentralized adaptive task-sharing algorithm in a distributed computing system is described. For the application considered, the simplicity and flexibility provided by software-based instrumentation are demonstrated, and its limitations are discussed. Quantitative results obtained from the implementation on an experimental distributed computing system consisting of VAX stations connected by a local area network are presented     

基于节点相似度的容错网格作业调度算法研究

为提高网格作业运行的成功率,研究了提高作业调度的可靠性的方法.研究表明,现有容错的网格作业调度算法多通过作业复制来降低节点的软硬件故障造成的作业失败的概率,它们既没有考虑作业的多个副本因共处的网络环境故障造成的同时失败,也没有考虑作业的多个副本由于所在节点缺乏相同的资源而同时失败.针对这一问题,提出了节点相似度的概念和计算方法,并将其应用到容错的网格调度算法中.提出的容错的调度算法将作业的多个副本分配到具有不同相似度的节点上运行,充分利用网格环境的分布性和异构性进一步减小作业失败的概率.     

Analysis of scheduling algorithms for master–slave systems

The master-slave paradigm finds important applications in many industrial settings. In the master-slave model considered in this paper a set of jobs is to be processed by a system of processors. Each job consists of a preprocessing task, a slave task and a postprocessing task that must be executed in this order. The pre- and postprocessing tasks are to be processed by a master processor, whereas the slave task is processed by a slave processor. We consider three different specifications for the relative order of pre- and postprocessing tasks; namely order preserving sequences, reverse order sequences, and sequences where no order constraint is imposed. For the problem of minimizing makespan in master-slave systems with multiple masters, we develop heuristic algorithms with good bounded performance, for all three order specifications. Our computational results indicate that the average performance of our heuristics is near optimal. Furthermore, we identify the production environment and workload characteristics that favor each order specification.     

Computational algorithms for solving the coefficient inverse problem for parabolic equations

Among inverse problems for partial differential equations, we distinguish coefficient inverse problems, which are associated with the identification of coefficients and/or the right-hand side of an equation using some additional information. When considering time-dependent problems, the identification of the coefficient dependences on space and on time is usually separated into individual problems. In some cases, we have linear inverse problems (e.g. identification problems for the right-hand side of an equation); this situation essentially simplify their study. This work deals with the problem of determining in a multidimensional parabolic equation the lower coefficient that depends on time only. To solve numerically a non-linear inverse problem, linearized approximations in time are constructed using standard finite difference approximations in space. The computational algorithm is based on a special decomposition, where the transition to a new time level is implemented via solving two standard elliptic problems.     

A large-scale distributed decision-making procedure for a single-machine scheduling problem

This paper presents a distributed scheduling procedure for a large-scale single-machine problem with precedence constraints, and identifies phenomena using large-scale distributed decision-making for a decomposable and distributed situation. The approach proposed exhibits efficient computational performance over a large-sized work load (23,000 jobs and 2,209,536 precedence constraints) in a distributed computing environment. We highlight three findings: (1) the communication burden originating from the large-scale problem can lead to performance loss while distributed agents collaborate to solve the problem, but after a threshold the computational gain by distribution offsets the loss; (2) when the problem size is sufficiently large, the real computation gain outperforms the expected gain by the number of agents (super-linear effect); and (3) when the number of precedence constraints of each agent differs, the slowest agent processing the largest number of precedence constraints restrains the computational performance (load imbalance). We believe that our research is the first distributed decision-making model that meets the requirements of distributed information, distributed decision authority, and distributed computation in a large-scale single-machine scheduling situation with precedence constraints.     

Fast parallel DNA-based algorithms for molecular computation: the set-partition problem

This paper demonstrates that basic biological operations can be used to solve the set-partition problem. In order to achieve this, we propose three DNA-based algorithms, a signed parallel adder, a signed parallel subtractor and a signed parallel comparator, that formally verify our designed molecular solutions for solving the set-partition problem.     

PPTM:一种面向异构系统的主动式任务映射方法

在数据高速增长的背景下,异构计算作为满足新兴应用不断提高的算力需求的有效途径,涌现了许多异构加速系统.在这些异构加速系统中,高效的任务映射是充分发挥加速器潜能提升应用程序性能的关键之一.先前工作提出了许多基于有向无环图如何最小化应用程序整体执行时间和最小化异构多处理器之间通信开销等高效的任务映射方法,这些工作通常采用将...     

Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints

This paper introduces models and algorithms for a static dial-a-ride problem arising in the transportation of patients by non-profit organizations such as the Austrian Red Cross. This problem is characterized by the presence of heterogeneous vehicles and patients. In our problem, two types of vehicles are used, each providing a different capacity for four different modes of transportation. Patients may request to be transported either seated, on a stretcher or in a wheelchair. In addition, some may require accompanying persons. The problem is to construct a minimum-cost routing plan satisfying service-related criteria, expressed in terms of time windows, as well as driver-related constraints expressed in terms of maximum route duration limits and mandatory lunch breaks. We introduce both a three-index and a set-partitioning formulation of the problem. The linear programming relaxation of the latter is solved by a column generation algorithm. We also propose a variable neighborhood search heuristic. Finally, we integrate the heuristic and the column generation approach into a collaborative framework. The column generation algorithm and the collaborative framework provide tight lower bounds on the optimal solution values for small-to-medium-sized instances. The variable neighborhood search algorithm yields high-quality solutions for realistic test instances.     

Petri nets and genetic algorithms for complex manufacturing systems scheduling

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.     

A learning-based methodology for dynamic scheduling in distributed manufacturing systems

To enhance productivity in a distributed manufacturing system under hierarchical control, we develop a framework of dynamic scheduling scheme that explores routeing flexibility and handles uncertainties. We propose a learning-based methodology to extract scheduling knowledge for dispatching parts to machines. The proposed methodology includes three modules: discrete-event simulation, instance generation, and incremental induction. First, a sophisticated simulation module is developed to implement a dynamic scheduling scheme, to generate training examples, and to evaluate the methodology. Second, the search for training examples (good schedules) is successfully fulfilled by the genetic algorithm. Finally, we propose a tolerance-based learning algorithm that does not only acquire general scheduling rules from the training examples, but also adapts to any newly observed examples and thus facilitates knowledge modification. The experimental results show that the dynamic scheduling scheme significantly outperforms the static scheduling scheme with a single dispatching rule in a distributed manufacturing system.