A New Task Scheduling Scheme Based on Genetic Algorithm for Edge Computing

With the continuous evolution of smart grid and global energy interconnection technology, amount of intelligent terminals have been connected to power grid, which can be used for providing resource services as edge nodes. Traditional cloud computing can be used to provide storage services and task computing services in the power grid, but it faces challenges such as resource bottlenecks, time delays, and limited network bandwidth resources. Edge computing is an effective supplement for cloud computing, because it can provide users with local computing services with lower latency. However, because the resources in a single edge node are limited, resource-intensive tasks need to be divided into many subtasks and then assigned to different edge nodes by resource cooperation. Making task scheduling more efficient is an important issue. In this paper, a two-layer resource management scheme is proposed based on the concept of edge computing. In addition, a new task scheduling algorithm named GA-EC(Genetic Algorithm for Edge Computing) is put forth, based on a genetic algorithm, that can dynamically schedule tasks according to different scheduling goals. The simulation shows that the proposed algorithm has a beneficial effect on energy consumption and load balancing, and reduces time delay.     

Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems

The task scheduling problem in heterogeneous distributed computing systems is a multiobjective optimization problem (MOP). In heterogeneous distributed computing systems (HDCS), there is a possibility of processor and network failures and this affects the applications running on the HDCS. To reduce the impact of failures on an application running on HDCS, scheduling algorithms must be devised which minimize not only the schedule length (makespan) but also the failure probability of the application (reliability). These objectives are conflicting and it is not possible to minimize both objectives at the same time. Thus, it is needed to develop scheduling algorithms which account both for schedule length and the failure probability. Multiobjective Evolutionary Computation algorithms (MOEAs) are well-suited for Multiobjective task scheduling on heterogeneous environment. The two Multi-Objective Evolutionary Algorithms such as Multiobjective Genetic Algorithm (MOGA) and Multiobjective Evolutionary Programming (MOEP) with non-dominated sorting are developed and compared for the various random task graphs and also for a real-time numerical application graph. The metrics for evaluating the convergence and diversity of the obtained non-dominated solutions by the two algorithms are reported. The simulation results confirm that the proposed algorithms can be used for solving the task scheduling at reduced computational times compared to the weighted-sum based biobjective algorithm in the literature.     

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.     

Improvised Seagull Optimization Algorithm for Scheduling Tasks in Heterogeneous Cloud Environment

Well organized datacentres with interconnected servers constitute the cloud computing infrastructure. User requests are submitted through an interface to these servers that provide service to them in an on-demand basis. The scientific applications that get executed at cloud by making use of the heterogeneous resources being allocated to them in a dynamic manner are grouped under NP hard problem category. Task scheduling in cloud poses numerous challenges impacting the cloud performance. If not handled properly, user satisfaction becomes questionable. More recently researchers had come up with meta-heuristic type of solutions for enriching the task scheduling activity in the cloud environment. The prime aim of task scheduling is to utilize the resources available in an optimal manner and reduce the time span of task execution. An improvised seagull optimization algorithm which combines the features of the Cuckoo search (CS) and seagull optimization algorithm (SOA) had been proposed in this work to enhance the performance of the scheduling activity inside the cloud computing environment. The proposed algorithm aims to minimize the cost and time parameters that are spent during task scheduling in the heterogeneous cloud environment. Performance evaluation of the proposed algorithm had been performed using the Cloudsim 3.0 toolkit by comparing it with Multi objective-Ant Colony Optimization (MO-ACO), ACO and Min-Min algorithms. The proposed SOA-CS technique had produced an improvement of 1.06%, 4.2%, and 2.4% for makespan and had reduced the overall cost to the extent of 1.74%, 3.93% and 2.77% when compared with PSO, ACO, IDEA algorithms respectively when 300 vms are considered. The comparative simulation results obtained had shown that the proposed improvised seagull optimization algorithm fares better than other contemporaries.     

Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines

In this work, we address the problem of scheduling a set of n non-preemptive tasks on m dedicated machines in order to minimise the makespan. For each task deterministic processing times and a specific processing machine are given, moreover a set of precedence constraints among the tasks are known. We present a heuristic and some lower bounds on the minimum makespan for a relevant case in manufacturing applications, namely when the precedence constraints form a caterpillar graph. A caterpillar is a directed tree consisting of a single directed path and leaf nodes each of which is incident to the directed path by exactly one incoming arc. A number of computational experiments are also performed in order to test the performance of the proposed solution algorithm.     

Scheduling the operations of a double-load crane in slab yards

This paper studies a double-load crane scheduling problem (DLCSP) in steel slab yards. A slab yard stores slabs in stacks. To prepare for use in production, some slabs need to be moved from one place to another. These movement tasks are performed by a double-load crane which can hold up to two slabs simultaneously. Given a set of tasks and possibly precedence relationships among them, the scheduling problem is to allocate the tasks to double-load operations and determine the schedule for the crane to perform the tasks so as to minimise the makespan. The problem is first formulated as a mixed integer linear programming (MILP) model with variables representing the order of tasks. Based on properties of the problem, it is then reformulated from a crane operation perspective. Computational experiments are carried out on practical data collected from a steel company. The results show that both models can solve practical sized problems optimally, with the second model being more efficient.     

Flow shop scheduling in serial multi-product processes with transfer and set-up times

Short-term production scheduling is a widely seen problem in multi-product batch operations. In this paper, an effective heuristic algorithm for scheduling a set of different tasks to be processed on serial processors is presented that provides an approach towards minimizing the entire makespan and improving productivity. Flow shops with an interstage storage policy, non-zero transfer times, and non-zero setup times are considered. The performance of the proposed algorithm was evaluated through numerous simulated problems. Statistical analysis of the output data indicates that in the situation containing up to seven tasks, the algorithm provides optimal or near optimal solutions and needs very short computation time. For a larger number of tasks, it gives up to 20% better solutions than a well-known existing algorithm.     

A duplication heuristic for static scheduling of tasks on distributed memory multiprocessors

Abstract

A task duplication heuristic, DSH, was proposed in [11]. The underlying concept of the task duplication heuristic is duplicating some tasks on processors such that the earliest start time of tasks on processors can be reduced, that is, tasks on processors can be executed sooner. This leads to a better scheduling length. In this paper, we propose a more general task duplication heuristic, bottom‐up top‐down duplication heuristic (BTDH), for static scheduling of directed‐acyclic graphs (DAGs) on distributed memory multiprocessors. The key difference between BTDH and DSH is the method used for duplicating tasks. BTDH allows tasks to be duplicated on processors even though the duplication of tasks will temporarily increase the earliest start time of some tasks. DSH only allows those duplications which will reduce the earliest start time of tasks. Simulation results show that, for coarse‐grain DAGs, the scheduling length of BTDH is almost the same as the scheduling length of DSH. However, for medium‐grain and fine‐grain DAGs, BTDH produces better scheduling length than DSH.     

Parallel asynchronous particle swarm optimization

The high computational cost of complex engineering optimization problems has motivated the development of parallel optimization algorithms. A recent example is the parallel particle swarm optimization (PSO) algorithm, which is valuable due to its global search capabilities. Unfortunately, because existing parallel implementations are synchronous (PSPSO), they do not make efficient use of computational resources when a load imbalance exists. In this study, we introduce a parallel asynchronous PSO (PAPSO) algorithm to enhance computational efficiency. The performance of the PAPSO algorithm was compared to that of a PSPSO algorithm in homogeneous and heterogeneous computing environments for small- to medium-scale analytical test problems and a medium-scale biomechanical test problem. For all problems, the robustness and convergence rate of PAPSO were comparable to those of PSPSO. However, the parallel performance of PAPSO was significantly better than that of PSPSO for heterogeneous computing environments or heterogeneous computational tasks. For example, PAPSO was 3.5 times faster than was PSPSO for the biomechanical test problem executed on a heterogeneous cluster with 20 processors. Overall, PAPSO exhibits excellent parallel performance when a large number of processors (more than about 15) is utilized and either (1) heterogeneity exists in the computational task or environment, or (2) the computation-to-communication time ratio is relatively small.     

A Spark Scheduling Strategy for Heterogeneous Cluster

As a main distributed computing system, Spark has been used to solve problems with more and more complex tasks. However, the native scheduling strategy of Spark assumes it works on a homogenized cluster, which is not so effective when it comes to heterogeneous cluster. The aim of this study is looking for a more effective strategy to schedule tasks and adding it to the source code of Spark. After investigating Spark scheduling principles and mechanisms, we developed a stratifying algorithm and a node scheduling algorithm is proposed in this paper to optimize the native scheduling strategy of Spark. In this new strategy, the static level of nodes is calculated, the dynamic factors such as the length of running tasks, and CPU usage of work nodes are considered comprehensively. And through a series of comparative experiments in alienation cluster, the new strategy costs less running time and lower CPU usage rate than the original Spark strategy, which verifies that the new schedule strategy is more effective one.     

Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

Scheduling UET-UCT tasks: branch-and-bound search in the priority space

The paper is concerned with the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered, the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theory and was originally inspired by the applications to multi-processor computer systems. It is well known that for both criteria the problem is NP-hard in the strong sense. The paper presents an implementation of the branch-and-bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments.     

Scheduling of wafer test processes in semiconductor manufacturing

This research focuses on solving a common wafer test scheduling problem in semiconductor manufacturing. During wafer testing, a series of test processes are conducted on wafers using computer-controlled test stations at various temperatures. The test processes are conducted in a specified order on a wafer lot, resulting in precedence constraints for the schedule. Furthermore, the assignment of the wafer lots to test stations and the sequence in which they are processed affects the time required to set up the test operations. Thus, the set-up times are sequence dependent. Four heuristics are developed to solve the test scheduling problem with the aim of minimizing the makespan required to test all wafers on a set of test stations. The heuristics generate a sorted list of wafer lots as a dispatching sequence and then schedule the wafer lots on test stations in order of appearance on the list. An experimental analysis and two case studies are presented to validate the proposed solution approaches. In the case studies, the heuristics are applied to actual data from a semiconductor manufacturing facility. For both case studies, the proposed solution approaches decrease the makespan by 23–45% compared with the makespan of the actual schedule executed in the manufacturing facility.     

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.     

Simultaneous versus sequential loading and scheduling of flexible assembly systems

A monolithic and a hierarchical approach is presented for loading and scheduling in a general flexible assembly system and a flexible assembly line. The system is made up of a set of assembly stations of various types each with limited working space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in a minimum time. In the monolithic approach loading and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced by solving the loading problem, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a standard job-shop problem. Mixed integer programming formulations are presented for simultaneous and for sequential loading and scheduling. Loading and scheduling with alternative or with single task assignments are considered. Numerical examples are included to illustrate and compare the two approaches proposed.     

Hybridization of genetic algorithm and fully informed particle swarm for solving the multi-mode resource-constrained project scheduling problem

In this article, the genetic algorithm (GA) and fully informed particle swarm (FIPS) are hybridized for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed hybrid genetic algorithm–fully informed particle swarm algorithm (HGFA), FIPS is a popular variant of the particle swarm optimization algorithm. A random key and the related mode list representation schemes are used as encoding schemes, and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. Furthermore, the existing mode improvement procedure in the literature is modified. The results show that the proposed mode improvement procedure remarkably improves the project makespan. Comparing the results of the proposed HGFA with other approaches using the well-known PSPLIB benchmark sets validates the effectiveness of the proposed algorithm to solve the MRCPSP.     

Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search

This work focuses on the scheduling problem of deadlock and failure-prone automated manufacturing systems, and presents a new scheduling method by combining a robust supervisory control policy and hybrid heuristic search. It aims to minimise makespan, i.e. the completion time of the last part. Based on the extended reach ability graph of the system, it establishes a new heuristic function and two dispatching rules to guide the search process for a schedule. By embedding a robust supervisory control policy into the search process, it develops a polynomial robust dynamic window search algorithm. Failure and repair events of unreliable resources may occur during the execution of a schedule obtained by the proposed algorithm and may make the schedule infeasible. To reduce the influence caused by them and ensure all parts to be finished, this work proposes two event-driven strategies. The first one suspends the execution of the parts requiring failed resources and those to be started until all failed resources are repaired and permits only those parts that have already been processed on working machines to be completed. The second one invokes the proposed algorithm to obtain a new schedule at the vertex generated after a resource failure or repair event and executes the new schedule. Both strategies are effective while the latter performs better at the expense of more computation.     

Multitasking scheduling problems with a rate-modifying activity

Motivated by the behavioral phenomena that occur while human operators are carrying out tasks, we study multitasking scheduling problems with a rate-modifying activity. In the problems, the processing of a selected task suffers from interruptions by other tasks that are available but unfinished, and the human operators regularly engage rest breaks during work shifts allowing them to recover or mitigate some of the negative effects of fatigue. The objectives are to respectively minimize: makespan, total completion time, maximum lateness, and due-date assignment related cost by determining when to schedule the rate modifying activity and the optimal task sequence in the presence of multitasking. Scheduling models and algorithms are proposed to solve the problems. The numerical examples are presented to illustrate the theorems and algorithms.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.