With the advancement of virtualization technologies, cloud computing environments have become more dynamic and real-time, enabling efficient resource allocation and task execution. However, real-time workflow scheduling in such environments remains a significant challenge due to the uncertainties in task execution time and data transfer delays. In the paper, the real-time and preemptive workflow scheduling problem is investigated. User requests are modelled to various workflows and arrive at the system stochastically. The time information about the workflows, such as the execution time and the data transfer delay are uncertain. Only the expected base values are given, and the real time information are certain only when these tasks are completed. The tasks in these workflows are allowed to be interrupted for at most one time. To address the problem, a real-time algorithm framework is proposed. The framework is integrated with a simulated annealing algorithm to obtain a high-quality feasible solution. A task interruption and resource re-allocation strategy is designed to interrupt tasks at the appropriate time and migrate interrupted segments of tasks to appropriate resources. Experimental results show that our approach achieves the best RPD of 0.424%, outperforming RMWS (12.866%) and GLS (14.862%).

As the airport terminal area becomes progressively crowded, costly delays and adverse environmental impact due to excessive fuel burn require effective aircraft routing and scheduling in the airport terminal area. Aircraft routing and scheduling in the airport terminal area refers to the safe and efficient movement of aircraft among airport facilities such as runways, aircraft stands and taxiways. It is a hybrid optimization problem that involves both the airport ground movement problem and the aircraft sequencing problem. The paper investigates the hybrid problem with constraints such as the safe distance between aircraft, queuing limit at the runways, and release time difference for sake of safety. The objective is to minimize the average taxiing time of the aircraft. A particle swarm optimization and Q-learning based aircraft routing and scheduling algorithm (PSO-QL-ARS) is proposed for the problem considered. The proposal adopts the main framework of PSO. It consists of three major components: the ideal shortest path algorithm, the semi-no-wait schedule generation method and the Q-learning based particle evolving method. The shortest path algorithm takes into consideration turning time according to the turning angles on the path and different taxiing speeds depending on the taxiway types. The semi-no-wait schedule generation method is presented to compute the feasible trajectory plan for an aircraft, including the waiting time at each vertex and the taxiing time on each taxiway. It attempts to place the waiting time of an aircraft on the aircraft stand. The Q-learning-based particle evolving method employs a Q-table to select the finest evolving action which is used to update the position of the given particle. The proposed algorithm is compared with four baseline algorithms. The experimental results show that the proposal outperforms the compared baseline algorithms in effectiveness and robustness.

Unmanned aerial vehicles (UAVs) are increasingly utilized in smart city applications, particularly for urban surveillance. UAVs can be provisioned as mobile surveillance to avoid various difficulties in ground operations and reduce extensive labor cost. However, their limited energy capacity restricts flight time and coverage, making it difficult to build a large-scale, long-term city-wide monitoring network. To address this problem, an ubiquitous public transportation network is introduced for UAVs to periodically recharge by landing on public transportation buses. We propose a novel public transportation-assisted UAV scheduling framework that leverages the existing bus network to enable recharging of UAVs. Two intertwined sub-problems are addressed: the UAV trajectory planning and the surveillance task offloading problems. The trajectory planning is modeled as a Traveling Salesman Problem (TSP) and it is solved via the Lin-Kernighan heuristic (LKH), decomposing the bus station network into sub-graphs for efficient routing. For task offloading, a time-slot-based scheduling method is proposed that dynamically assigns UAVs to monitor points of interest (PoIs) while ensuring energy constraints and full coverage. Experimental results demonstrate that the proposal outperforms baseline algorithms, achieving a 1.72%-3.46% average extension in system lifetime compared to state-of-the-art baselines, while maintaining computational efficiency (average runtime: 277.57 ms). The robustness of the proposal is further validated across diverse testing instances with various parameter settings.

In the paper, the Unmanned Aerial Vehicle (UAV) path planning and task offloading problem in UAV-assisted mobile edge computing (MEC) systems is investigated. A bi-criterion ant colony optimization (bi-ACO) framework is proposed for the considered problem with the objectives of minimizing the total cost and the completion time, meanwhile satisfying the energy, deadline, location, and priority constraints. In the bi-ACO framework, multiple heterogeneous colonies are introduced with different preferences of objectives. Each colony maintains five pairs of pheromone matrices for constructing feasible solutions. Besides the colony settings, three key components of bi-ACO are delicately designed: feasible solution generation method (FSGM) to construct a feasible solution, solution division method (SDM) to improve obtained solutions of good quality, and pheromone update method (PUM) to updates pheromone matrices by pheromone evaporation operation and pheromone enhancement operation based on the preferences of colonies. Four Pareto-based metrics are introduced to evaluate the performance of the compared algorithms. Experimental results show that the proposal outperforms the compared baseline algorithms in effectiveness and robustness.

The resource-constrained task scheduling problem has been one of the popular research topics in cloud computing systems. By employing the dynamic voltage and frequency scaling (DVFS) techniques, the task scheduling can be further constrained by energy consumption. The paper investigates the DAG task scheduling considering both the resource and energy constraints in heterogeneous distributed systems. The objective is to minimize the scheduling length. An energy-constrained task scheduling framework is employed, where tasks are initially scheduled according to their upward rank values. Then two heuristics are proposed to improve the initial solution, namely, the simulated annealing local search method and the frequency adjustment method. Experiments are conducted by testing a large number of instances with multiple parameter settings, and the results show that the proposed algorithms are effective and efficient.

When it comes to the fifth generation, collaborative edge computing is preferred for offloading computation-intensive tasks of low-latency applications in Internet of Things. In this paper, we consider the partial task offloading problem where tasks can be divided into subtasks and offloaded to nearby devices. The flow scheduling problem is integrated in the offloading process, i.e., multiple and conflicting route paths are considered. We propose the latency-aware partial task offloading framework (LaPTOF) for the considered problem. LaPTOF integrates a weighted priority ranking strategy (WPRS) which generates multiple solutions with different weights on task arrival time and the task processing time. A feasible solution generation method (FSGM) is designed where the best offloaded proportion of tasks are computed, and the appropriate offloaded devices and offload paths are determined. The proposed LaPTOF has an advantage in providing a scheduling plan that minimizes total completion time of task offloading in a shorter duration. The experimental results show that the proposal is suitable for the considered problem compared with JPOFH and its variants on both effectiveness and efficiency.

The UAV-enable Mobile Edge Computing (MEC) systems and Vehicular Ad-hoc Network (VANET)-supported applications are very popular topics these days. The paper considers the vehicular task offloading problems for the Software-Defined Vehicular Network (SDVN)-supported services in the UAV-enabled MEC system. In the considered problem, one UAV and one edge server (ES) are provisioned for the workload from the moving vehicles in a certain region. For each vehicle in the region, it would periodically submit requests to the UAV-enable MEC system until it leaves the region. Each request will be taken as a computation task and could be offloaded locally on the vehicle, the UAV, or the ES. Multiple communication and energy consumption models are employed to formulate the problem model. The objectives are to minimize the total time delays and the energy consumption. A greedy heuristic based dynamic scheduling framework is proposed for the problem under study. Simulated experiments are delicately designed with dynamic traffics, various road and building distributions. Experimental results show that the proposal is more effective than the compared algorithm.

How to effectively utilize the limited battery capacities is crucial for IoT (Internet of Things) devices. In many applications, it is not necessary to keep every device always active. In other words, devices should be periodically activated and slept to reduce energy consumptions. In this paper, the problem under study with device active time minimization is mathematically modelled using ILP (Integer Linear Programming). After analyzing the bounds of the variables, the IILP (Improved Integer Linear Programming) algorithm is proposed to solve the considered optimization problem in polynomial time whereas it cannot guarantee to obtain the optimal solution. Moreover, the traverse-based TP (Two Pointers) algorithm is developed to obtain the optimal solution with much longer computation time. By comparing IILP to TP over a lot of instances, experimental results show that IILP is much faster than TP whereas TP outperforms IILP in effectiveness.

The edge-cloud computing systems are widely used to support various computation services. In this paper, we consider a dynamic task offloading problem in the edge-cloud computing system with multiple independent and stochastic arriving tasks. The system periodically schedules and offloads tasks to heterogenous resources in consideration of the required transmission delays and computation times. Our goal is to minimize the sum of weighted response times of all the tasks. A greedy local search based online offloading framework is proposed for the problem under study, which dynamically assigns tasks to the appropriate destination (edge servers or cloud servers) and preemptively allocates computing resources to each task according to its latency-sensitivity. Evaluation experiments are delicately designed on a number of testing instances with various parameter settings. Experimental results indicate that the proposal algorithm is more effective than the compared algorithms.

Task scheduling in heterogenous and distributed systems for the directed acyclic graph (DAG) based applications has been widely studied. In DAG task scheduling problems, a set of distributed tasks with dependencies are dispatched to appropriate computing instances. The objective is to obtain the feasible schedule with the minimal schedule length, i.e., makespan. In this paper, we propose a task duplication based clustering framework for the problem under study. We employ the task duplication scheme in the framework which allows task clusters contain duplicated tasks in order to reduce the communication cost. A selection matrix is introduced to record the candidate tasks to generate clusters. Multiple feasible task clustering solutions are obtained based on the selection matrix and among which the best one with the minimal makespan is output. Experimental results indicate that the proposal outperforms compared algorithms on both effectiveness and robustness.

In this paper, we investigate the task scheduling problem in the UAV-enable Mobile Edge-Computing (MEC) system with the objectives of minimizing the cost and the completion time. A NSGA-II algorithm is proposed for the problem under study. The solution is represented as a two-dimension location sequence. Major components of NSGA-II are delicately designed including the feasible solution generation method (FSGM) and genetic operations of crossover, mutation and selection. Three strategies are introduced in FSGM. A simulated annealing local search is integrated into the crossover operation, and meanwhile two novel mutation methods are proposed. The Pareto-based metrics are introduced to evaluate the performance of the compared algorithms. Experimental results show that the proposal is more effective and robust than the three existing algorithms.

In this paper, we investigate the dynamic task scheduling problem with stochastic task arrival times and due dates in the UAV-based intelligent on-demand meal delivery system (UIOMDS) to improve the efficiency. The objective is to minimize the total tardiness. The new constraints and characteristics introduced by UAVs in the problem model are fully studied. An iterated heuristic framework SES (Stochastic Event Scheduling) is proposed to periodically schedule tasks, which consists of a task collection and a dynamic task scheduling phases. Two task collection strategies are introduced and three Roulette-based flight dispatching approaches are employed. A simulated annealing based local search method is integrated to optimize the solutions. The experimental results show that the proposed algorithm is robust and more effective compared with other two existing algorithms.

Different data transmission times, processing times which are difficult to predict and node-dependent access times make MapReduce task scheduling rather complex. In this article, we consider the problem of scheduling MapReduce tasks to heterogeneous geo-distributed data centers to minimize the total tardiness. A new architecture is constructed to analyze data in the considered scenario. We model distinct data transmission levels, inter- and intra- data centers and heterogeneity of nodes mathematically. An algorithm framework is proposed to schedule MapReduce tasks to heterogeneous nodes in geographically distributed data centers. The proposed algorithm is suitable for both Hadoop MRv1 and MRv2. In terms of the number of idle containers detected in each heartbeat, the same number of tasks are selected from a sorted job sequence. For the map and reduce phases, two measurements are developed with data locality and completion time, respectively, based on which the classical Hungarian algorithm is adopted to optimally assign selected tasks to corresponding idle containers. Components and parameters of the proposal are statistically calibrated over a large set of random instances. A comparison of the proposed algorithm to existing methods for similar problems is carried out. Experimental results demonstrate the proposal is effective for the considered problem.

Electricity prices differ during different time periods and change from place to place. Cloud workflow applications often require geo-distributed data which is transmitted among heterogeneous servers in intra- and inter- data centers. Such varying electricity prices and data transmission time bring great challenges when optimizing the energy cost for scheduling tasks in workflow applications to heterogeneous servers in cloud data centers. In this article, we minimize the total electricity cost in a deadline constrained energy-aware workflow scheduling problem with data being geographically distributed across data centers. A scheduling algorithm is proposed. Strategies are developed to sequence workflow applications, divide deadlines and sort tasks. An adaptive local search method is presented to improve solutions during the search process which dynamically balances intensification using neighborhood structures of increasing size. Components and parameter values are statistically calibrated over a comprehensive set of random instances. The proposed algorithm is compared to modified classical algorithms for similar problems. Experimental results demonstrate the effectiveness of the proposal for the considered problem.

The application of unmanned aerial vehicle (UAV) to achieve precision irrigation in agriculture is a hot research topic in the industry. However, much spay and much leakage of pesticide are tricky for the current UAV-based irrigation methods to deal with. In this paper, we propose a new UAV-based irrigation system for precision agriculture. First, considering that different areas in the same farmland may have different pesticide shortage, a map preprocess strategy is introduced to divide the entire farmland into pieces. Second, we establish a UAV precision irrigation model and put forward an adaptive and fast dynamic ant colony optimization (AFD-ACO) algorithm to minimize the longest flight path with the lowest energy consumption and pesticide residues. In order to promote the efficiency and the optimization effect, we utilize the scent pervasion rule to make the global map preprocessed and the neighborhood adaptive search policy to accomplish planning work. Finally, comparing with other two ACO-based algorithms, the proposed algorithm is proved to be effective for the research problem, especially when the more pieces the farmland is divided, the better our solution performs.

To improve the flexibility and efficiency of the logistics distribution process, a new logistics distribution model, namely Community Logistics System(CLS) model, is established. In this paper, we consider that it is impossible to transport every package to the express cabinet closest to the customer. Hence, the optimizing objective of this problem is to minimize the total fetching distance. In addition, considering the capacity constraints of express cabinets, a reasonable allocation strategy is designed. We propose a Simulated Annealing Genetic (SAG) algorithm to solve the problem. In order to promote the efficiency and the optimization effect, we generate the first generation population by using Simulated Annealing algorithm instead of using random selection as in most case. By comparing with other two heuristic algorithm (SA and GA), the proposed algorithm is proved to be robust and effective for the research problem.

A fuzzy workflow scheduling problem is investigated with fuzzy temporal parameters, such as the fuzzy task processing times, fuzzy data transmission times and the fuzzy due dates. In the considered problem, the resources are elastic cloud resources with multiple price structures. Due to the fuzzy temporal parameters, the deadline constraint cannot be ensured. Therefore, we formulate a triangle fuzzy number-based workflow scheduling problem model with the soft deadline constraint. A greedy local search method is proposed. The objectives are minimizing the total rental cost and the average dissatisfaction degree. The Pareto-based metrics are introduced to evaluate the performance of the compared algorithms. Experimental results show that the proposal is more effective and robust than the two existing algorithms.

Abstract This paper examines a scheduling problem with heterogeneous logistics unmanned aerial vehicles (UAVs) in urban environment. Different from traditional vehicle routing problem (VRP), it introduces some new characteristics such as the loading capacity, the maximum flight time and the flight speed. As a variant of VRP, the considered scheduling problem is known to be an non‐deterministic Polynomial (NP)‐hard problem. The UAV scheduling problem model with the heterogeneous UAV settings is formulated first. Secondly, a genetic‐based algorithm framework is presented for solving the scheduling problem, in which the encoding/decoding method, the initial population generation method and genetic operations are delicately designed. In order to reduce the search space and faster the execution of this algorithm, a weight‐based loading method is adopted. For the purpose of performance evaluation and statistical analysis, the proposed algorithm is compared with the other two existing algorithms. The experimental results show that the presented algorithm can solve this problem efficiently.

In the wireless sensor networks, it is a challenging issue to protect the data privacy from curious users while providing top-k query services. In this paper, a novel privacy-preserving and collusion-resisting top-k query processing interactive protocol is proposed for WSNs. To the best of our knowledge, it is the first work providing the privacy preservation and collusion resistance simultaneously in top-k query processing in WSNs. Data encryption with different private keys, the bloom filter and HMAC are adopted to achieve data privacy preservation even there are a few sensors colluding with the adversaries. During the interactive procedures of the query processing, two rounds of secure interactions between the sink and sensors are performed to obtain the query results. The protocol analysis indicates that the protocol can preserve data privacy even a few sensors collude with the adversaries, while the experiment result shows that the proposed protocol has good performance on network communication cost.

As an complement of cloud computing, fog computing provides computing services with closer geographic distance and focuses on distributed computing. In this paper, we consider the bi-objective task scheduling problem with heterogeneous resources in a fog-cloud computing system. There are two minimization objectives: energy consumption and delay. We formulate a workload allocation problem model involving fog devices (FDs) and the cloud servers (CSs). The computing resources are heterogeneous on the energy consumption, processing capability and delay. An energy-aware greedy heuristic algorithm (EG) is developed to search for Pareto Front solutions. For the problem under discussed, Experimental results indicate that the proposal algorithm is effective and robust compared with the comparison algorithm.

We investigate a workflow scheduling problem with stochastic task arrival times and fuzzy task processing times and due dates. The problem is common in many real-time and workflow-based applications, where tasks with fixed stage number and linearly dependency are executed on scalable cloud resources with multiple price options. The challenges lie in proposing effective, stable, and robust algorithms under stochastic and fuzzy tasks. A triangle fuzzy number-based model is formulated. Two metrics are explored: the cost and the degree of satisfaction. An iterated heuristic framework is proposed to periodically schedule tasks, which consists of a task collection and a fuzzy task scheduling phases. Two task collection strategies are presented and two task prioritization strategies are employed. In order to achieve a high satisfaction degree, deadline constraints are defined at both job and task levels. By designing delicate experiments and applying sophisticated statistical techniques, experimental results show that the proposed algorithm is more effective and robust than the two existing methods.

To improve the flexibility and efficiency of the logistics distribution system, a new type of logistics distribution mode, namely the Unmanned Aerial Vehicle and Shared Reception Box (UAV-SRB) logistics distribution mode, is studied. In this paper, we consider logistics scheduling problem of using multiple homogeneous UAVs to transport a batch of packages from one logistics center to multiple SRBs. The optimizing objective of this problem is to minimize the average mission execution time of UAVs. In addition, considering the capacity constraints of UAVs, a corresponding single-objective mathematical model is established. Combined with the actual logistics situation, we propose an Adaptive Tabu Search Algorithm (ATSA) to solve this problem. In order to improve the optimization performance, the algorithm designs adaptive tabu length and divides neighborhood space into several subsets according to different destinations. By comparing with other two heuristic algorithms (LSA and SA), the proposed algorithm is proved to be robust and effective for the research problem.

To reduce the operating cost, leasing appropriate amount of public resources becomes a popular practice among small and medium sized enterprises. Many hybrid cloud workflow management systems (HCWMSs) have been developed to provision applications on both local and rented resources. One of the critical issues in the HCWMS is the dynamic resource allocation for stochastically arriving requests. Therefore, we propose a dynamic interval scheduling based heuristic for the resource allocation problem, in which stochastic requests are taken as a set of linearly dependent tasks and distributed to idle and feasible time slots on multiple virtual machines (VMs), either local or rented VMs. The objective is to minimize the idle time slots on the rented VMs, which is relative to the renting cost of VMs, especially for the on-demand pricing structure. Requests arrive at the same time are taken as a batch of tasks to schedule. Tasks are scheduled batch by batch, obeying the precedence constraint and the deadline constraint. We develop a fast heuristic integrated with an interval scheduling to obtain feasible and effective solutions. Three interval scheduling method are proposed and compared: Max Interval Number Scheduling (MINS), Max Working Time Scheduling (MWTS) and Select-the-better Method (STBM). The experimental results show that the interval scheduling based heuristic can reduces the cost of renting VMs.

We consider a special workflow scheduling problem in a hybrid-cloud-based workflow management system in which tasks are linearly dependent, compute-intensive, stochastic, deadline-constrained and executed on elastic and distributed cloud resources. This kind of problems closely resemble many real-time and workflow-based applications. Three optimization objectives are explored: number, usage time and utilization of rented VMs. An iterated heuristic framework is presented to schedule jobs event by event which mainly consists of job collecting and event scheduling. Two job collecting strategies are proposed and two timetabling methods are developed. The proposed methods are calibrated through detailed designs of experiments and sound statistical techniques. With the calibrated components and parameters, the proposed algorithm is compared to existing methods for related problems. Experimental results show that the proposal is robust and effective for the problems under study.

In the paper, we consider the dynamic, elastic and flexible task scheduling problem in hybrid clouds. Tasks are linearly dependent, compute-intensive, stochastic, deadline-constrained and executed on elastic and distributed cloud resources. The objective is to finish all jobs before their deadlines with renting virtual machines as less as possible. Firstly, we propose two simple and fast dispatching rules. Then we develop an efficient local search heuristic and its modified version with a rescheduling component. All proposed heuristics are tested and evaluated through experiments. Experimental results show that the proposals are effective for the problem under study.

Cloud has become an attractive computing platform which offers seemly unlimited and computing resources to public. From perspective of data centers which offer cloud services, however, computing resources are limited and operating cost restricts cloud service quality. In order to balance between cost and service quality, the scheduling module, as the core component of the management system of data centers, should be able to sophisticatedly schedule computing jobs with high utilization of computing resources. In the paper, we present efficient heuristics for the scheduling module to yield elastic and flexible schedule plans for desired service quality with less cost, which can automatically scale up/down computing instances in response to workload over time. Computing jobs are specified as flowshop type jobs, which are multi-stage tasks with linear processing routes. Jobs are assigned hard deadlines according to service quality. The goal is to ensure all jobs are finished within their deadlines with the minimum number of elastic computing instances. Experimental results show that the proposed heuristics can effectively improve utilization of computing resources and guarantee cloud service quality.

In this paper, we consider the widespread multi-stage job scheduling problem (e.g., in big data processed by MapReduce) in which jobs arrive at hybrid cloud systems stochastically. The objective is to minimize the number of elastic computing instances. Along with hard deadlines of jobs, the problem under study is NP-hard in strong sense. In terms of initial job priorities, timetables are constructed by adjusting job priorities adaptively and generating feasible schedules iteratively. Job sequences are generated by two simple dispatching rules. A fast local search heuristic and a rescheduling process are developed for improving the obtained sequences. Experimental results show that the proposed heuristics improve the utilization of computing resources effectively while meeting the cloud service quality requirements.

In this paper, an effective metaheuristic is developed for the no-wait job shop problem with the objective of makespam minimization, which is strongly NP-hard. The problem is usually decomposed into a sequencing sub-problem and a timetabling one. A partial delay timetabling method is constructed by combining the "as early as possible" strategy with the "as late as possible" rule. By integratiiig the variable neighborhood structure, a new Local Search method CLMVN (Complete Local Search with Memory and Variable Neighborhood structure) is presented for the sequencing problem. Experimental results show that CLMVN outperforms CLLM (the best algorithm for the considered problem so far) on average with less computation time.

The no-wait job shop problem that exists with makespan minimization is well known to be a strongly NP-hard problem. In this paper, the properties of the problem are analyzed according to its characteristics. The problem is remodeled based on the introduced time difference. A traditional framework is adopted by decomposing the problem into two subproblems: the sequencing and the timetabling problems. An efficient Shift Penalty-Based Timetabling method is proposed, which constructs two initial timetables from time difference-based sets and improves them by an investigated timetable tightening method. A modified complete local search with memory is presented for the sequencing problem. The whole algorithm is tested on benchmark instances and compared with the two best existing algorithms. Computational results show that the proposed algorithm performs well on both effectiveness and efficiency.

In Database-as-a-Service (DBaaS), a large number of tenants share DBaaS resources (CPU, I/O and Memory). While the DBaaS provider runs DBaaS to "share" resources across the entire tenant population to maximize resource utilization and minimize cost, the tenants subscribe to DBaaS at a low price point while still having resources conceptually "isolated" according to service level agreements (SLAs). To optimize this dichotomy of goals, we propose a dynamic resource allocation framework that periodically re-allocates resources to tenants to maximize resource utilization while tolerating a low risk of SLA violations. We model the resource allocation problem as a modified unbounded knapsack problem. The model introduces an additional fairness constraint to assign residual resources to active tenants, while avoiding that few tenants consume all residual resources. Performed experiments demonstrate the effectiveness and efficiency of the proposed allocation algorithm for a synthetic workload with burstiness and predicted tenant behavior.

In this paper, the Pre-emptive Resource-Constrained Project Scheduling Project (PRCPSP) is considered. The paper mainly focuses on the problem 1_PRCPSP, where a maximum of one interruption per activity is allowed. A time-fragment linked-list method (TFLLM) is proposed to generate an effective solution for a given precedence-feasible activity list. Based on the TFLLM, an evolutionary algorithm is developed with the objective of makespan minimization. Computational experiments on the standard J30 and J60 sets show that the proposed algorithm can perform better than the compared approach in literature for the pre-emptive cases.

In the paper, a similarity based ant-colony algorithm (SACO) is proposed for the permutation flowshop scheduling problems with total flowtime minimization, which is known as NP-hard. By applying the space mapping method which is testified to be reasonable, it is proved theoretically that the deposit factor ρ has hardly impact on the ACO evolutionary availability, and ρ = 0.5 is reasonable for the ACO. Similarity is defined to discover the promising sequence for solution improvement. A new solution construction method is proposed, which is stated to be better than that of another very effective ant-colony algorithm. Experimental results show that SACO outperforms the other compared seven algorithms, including three rather recent effective algorithms and four famous ant-colony algorithms. The similarity indeed helps the SACO to find the promising sequence for solution improvement, which makes the SACO be effective.

In this paper, a composite heuristic algorithm is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are well known NP-hard. Besides initialized by LR(n/m), solution of the proposal is developed by iteration of FPE or BPE alternatively. Perturbation is applied to escape from the local optimization when no improvement can be obtained during the development procedure. Good structures in the sequence can be kept during the perturbation. Ties with no improvement can be broken up during the perturbation. Experimental results show that the proposal is rather suitable for large-sized problems and outperforms the other recent and effective algorithms considered on benchmark instances on average.

In the paper, the no-wait job shop problem with makespan minimization is considered, which is decomposed into the sequencing problem and the timetabling problem. Based on the non-delay timetabling procedure and the inverse timetabling procedure, an enhanced timetabling procedure is constructed by shifting jobs leftwards or rightwards to obtain better timetables. The two sub-problems are solved independently by traditional methods. However, a meta-heuristic algorithm MCLM (modified complete local search with memory) is presented to solve the sub-problems integrally in this paper. Experimental results show that MCLM outperforms all the existing effective algorithms for the considered problem with little more computation time.