To overcome vendor lock-in and reliability issues in single-cloud deployments, organizations increasingly adopt multi-cloud environments. However, scheduling Spark workflows across heterogeneous clouds under simultaneous deadline and budget constraints remains challenging due to resource diversity, variable pricing, and cross-cloud data transfers. We propose the Deadline Budget Spark Workflow Scheduling to Multi-Cloud (DB-SWSMC) algorithm, a novel scheduling algorithm combining heuristic initialization with simulated annealing optimization to: (1) efficiently allocate resources while balancing cost-time tradeoffs, (2) handle intra/inter-cloud data dependencies, and (3) rigorously enforce constraints. Evaluations across five workflows and compared against existing algorithms (HBDCWS, DBCS, and BDHEFT). Experimental results demonstrate that DB-SWSMC outperforms existing algorithms by 20-40% in cost efficiency and 15-80% in success rates, especially under tight budget and deadline constraints.

Recently, the widespread use of smart devices for Internet of Things has led to a massive growth in data and information on the World Wide Web. However, multiple sources from the Web often provide conflicting descriptions for the same objects, thereby complicating the task of truth discovery, especially when sources may copy information from others. Existing approaches typically neglect the dependence and accuracy of these sources, resulting in low accuracy and efficiency in truth discovery. To solve the problem, we proposeDepenBaye, a source-dependent truth discovery framework, which incorporates Bayesian probability, the Simulated Annealing method, and the expectation maximization (EM) method. By evaluating the copy probability of sources based on false claims, reliable sources are identified with a simulated annealing method to improve efficiency. According to the EM method, source reliability and claim confidence are iteratively calculated to discover the latent truth.DepenBaye’s performance has been validated through extensive experiments, which outperforms existing approaches in efficiency and effectiveness.

In the era of Big Data and generative artificial intelligence (AI), discovering the truth about various objects from different sources has become a pressing topic. Existing studies primarily focus on dependent sources with conflicting information, where sources may copy information from each other. However, real-world scenarios are often more complex, with dynamic dependence relationships among sources over time. This complexity makes it much more difficult to discover the truth. One of the key challenges centers on measuring the dynamic dependence among sources. To address this challenge, we have developed three models:$Depen\_{S}imple$,$Depen\_{C}omplex$, and$Depen\_{D}ynamic$. These models are based on the Hidden Markov Model (HMM) and are designed to handle different types of dependencies, namelysimple source dependence,complex source dependence, anddynamic source dependence. Based on the constructed models, we propose a generic framework for discovering the latent truth which are evaluated by three HMM-based methods. We conduct extensive experiments on three real-world datasets to evaluate the performance of the proposed methods, and the results demonstrate that all three methods achieve high accuracy over the state-of-the-art methods.

Vehicular Edge Metaverse (VEM) is a new paradise supported by the Internet of Things, AI, and wireless communication technologies which provide various Virtual Vehicle Services (VVSs), where users can immerse and enjoy their spiritual world. To provide various VVSs for users, there is a significant increase in computational demands. The limited computing resource available on the vehicles are insufficient to handle the massive volume of tasks and the diverse needs of users. Edge nodes could provide more services than vehicles but longer transmission time and the cloud node can provide more services than edge nodes with longer transmission time. To provide better experiences for users, we use a three-layer (cloud-edge-vehicles) resource framework in VEM. In this paper, we construct a VEM offloading framework with communication and computation capabilities for metaverse services. It considers tasks with different requirements and comprehensively evaluates offloading decisions and resource allocation to maximize user's satisfaction in the metaverse and minimize the energy consumption of vehicles. To achieve this, a two-stage offloading algorithm based on a hybrid heuristic approach is proposed, aiming to find the Pareto optimal solution for the bi-objective optimization problem. Finally, experiments demonstrate that the proposed algorithm over-performs other algorithms with real dataset, validating that the proposed algorithm can effectively enhance user service satisfaction and reduce energy consumption.

In this paper, we investigate the problem of minimizing the total energy consumption for serverless functions (SFs) while ensuring that the cold start probability of each SF remains below a specified threshold. In serverless computing, containers are reused to reduce the occurrence of cold starts, which increases the static energy consumption and decreases the dynamic energy consumption of physical machines (PMs). The trade-off between cold start reduction and energy consumption introduces significant challenges, especially considering that container states (idle, cold start, and running) have distinct energy characteristics. To address these challenges, we propose a container-state-aware energy consumption model that accurately captures the dynamic energy characteristics of PMs. Furthermore, we develop an enhanced Bayesian Optimization-Based Energy Consumption Minimization (BOECM) algorithm, which determines the optimal reuse times for different serverless functions (SFs) by decomposing the high-dimensional search space into a series of lower-dimensional sub-problems. In addition, several tailored heuristic strategies are proposed for request allocation and container deployment. The proposed BOECM algorithm is compared with several existing heuristic and meta-heuristic algorithms for similar problems. Experimental results demonstrate that the proposed method significantly reduces total energy consumption, maintains cold start probabilities within acceptable limits, and outperforms the baselines.

Uncrewed Aerial Vehicles (UAVs) with caching capabilities present a flexible and scalable approach for efficient content delivery in wireless communication environments with high demand. However, the challenges posed by the limited energy and storage capabilities of UAVs significantly affect content delivery efficiency. In this paper, we consider the problem of UAV-assisted content delivery across multiple base stations, with the aim of reducing content acquisition delays by jointly optimizing UAV trajectory, cache replacement, and transmission power. A Dual-phase Deep Reinforcement Learning (DDRL) framework is proposed, integrating real-time decision making with offline training to adapt dynamic user demands and multi-BS configurations. The Particle Swarm Optimization (PSO) algorithm is incorporated to improve UAV caching performance. The simulation results demonstrate that the DDRL framework achieves up to a 8% reduction in latency and a 5% improvement in cache hit rate compared to the best baseline algorithm, showcasing its efficiency in UAV-assisted content delivery.

The Internet of Things (IoT) is becoming integral to our daily lives, facilitating data collection and analysis for informed decision-making as devices generate vast amounts of data. The transition from Mobile Cloud Computing (MCC) to Mobile Edge Computing (MEC) is increasingly favored for its benefits, including reduced communication latency and efficient bandwidth utilization; however, offloading tasks to the MEC encounters challenges related to data privacy and energy consumption. This study presents an advanced Deep Reinforcement Learning (DRL) based security-aware data offloading and resource allocation model for industrial IoT devices that prioritizes security while effectively managing their computational and radio resources. The model aims to minimize computation latency and energy consumption, which we address using a deep learning optimization strategy. Furthermore, an AES-based security layer is integrated to meet data security needs. Experimental results show that our model significantly reduces offloading overhead compared to both local execution and full offloading, while also demonstrating exceptional scalability for large-scale IoT deployments.

Multimodal sentiment analysis uses text, visual, and audio data to assess user sentiment, while both the discrimination power of modalities and sample distributions over categories remain imbalanced in practice. To address these challenges, we propose a Multi-grained Perception Model with Perceived Contrastive Focal loss, denoted MGSA1. More specifically, we design a Multi-grained Cross-modal Attention Perception (MCP) module, which employs coarse-grained and fine-grained cross-modal attention to deeply explore the complementary semantics between modalities, thereby modeling sentiment polarity and intensity by fusing text-video and text-audio data, respectively. Modeling sentiment polarity and intensity helps alleviate feature interference between modalities due to their differing discriminative power. Furthermore, the Perceived Contrastive Focal (PCF) loss is designed to address the challenge of unbalanced samples. We enhance the focal loss by incorporating inverse document frequency to dynamically weight samples within each class. Furthermore, information noise contrastive estimation is introduced to replace the class probability predictions in the enhanced focal loss, thereby more effective differentiation between positive and negative samples. Experiments on the MOSI and MOSEI datasets demonstrate that MGSA outperforms all baselines across a range of metrics.

In the era of data information explosion, there are different observations on an object (e.g., the height of the Himalayas) from different sources on the web, social sensing, crowd sensing, and data sensing applications. Observations from different sources on an object can conflict with each other due to errors, missing records, typos, outdated data, etc. How to discover truth facts for objects from various sources is essential and urgent. In this paper, we aim to deliver a comprehensive and exhaustive survey on truth discovery problems from the perspectives of concepts, methods, applications, and opportunities. We first systematically review and compare problems from objects, sources, and observations. Based on these problem properties, different methods are analyzed and compared in depth from observation with single or multiple values, independent or dependent sources, static or dynamic sources, and supervised or unsupervised learning, followed by the surveyed applications in various scenarios. For future studies in truth discovery fields, we summarize the code sources and datasets used in above methods. Finally, we point out the potential challenges and opportunities on truth discovery, with the goal of shedding light and promoting further investigation in this area.

Addressing the bias problem in multimodal zero-shot learning tasks is challenging due to the domain shift between seen and unseen classes, as well as the semantic gap across different modalities. To tackle these challenges, we propose a multimodal disentangled fusion network (MDFN) that unifies the class embedding space for multimodal zero-shot learning. MDFN exploits feature disentangled variational autoencoder (FD-VAE) in two branches to distangle unimodal features into modality-specific representations that are semantically consistent and unrelated, where semantics are shared within classes. In particular, semantically consistent representations and unimodal features are integrated to retain the semantics of the original features in the form of residuals. Furthermore, multimodal conditional VAE (MC-VAE) in two branches is adopted to learn cross-modal interactions with modality-specific conditions. Finally, the complementary multimodal representations achieved by MC-VAE are encoded into a fusion network (FN) with a self-adaptive margin center loss (SAMC-loss) to predict target class labels in embedding forms. By learning the distance among domain samples, SAMC-loss promotes intraclass compactness and interclass separability. Experiments on zero-shot and news event datasets demonstrate the superior performance of MDFN, with the harmonic mean improved by 27.2% on the MMED dataset and 5.1% on the SUN dataset.

Knowledge-based visual question answering (KB-VQA) requires reasoning about the visual grounding relations between the images and questions by incorporating external knowledge. Existing works typically retrieve knowledge from knowledge graphs by leveraging global multimodal representations of image–text pairs for graph convolution, which neglect contextual clues at hop granularity, resulting in suboptimal spreading and leveraging of contextual information. To this end, we propose a multi-hop graph reasoning network (MGRN) for KB-VQA, which consists of a knowledge graph constructor (KGC) module, a semantic-instructed graph reasoning (SGR) module, and an answering module. MGRN exploits multimodal semantics from given images and questions as instructions for graph reasoning to obtain the knowledge representation from either the scene graph or knowledge base. Specifically, KGC fuses the scene graph with triplets from ConceptNet and Comet to construct a contextual knowledge graph for retrieving knowledge representation. Furthermore, SGR conducts multi-hop graph reasoning to select top- K knowledge items for answering by passing and filtering interplay messages on contextual knowledge graphs under the guidance of multimodal semantic representation. Extensive experiments conducted on two public datasets show the effectiveness and outperformance of our method.

In Kubernetes-based Cloud Native platforms, allocating containers to micro-services elastically according to workload changes is benefical to minimizing resource cost while stabling response times. However, inaccurate performance models for multi-container systems, along with coarse-grained container-based allocation, cause performance fluctuations. In this paper, deep learning, traditional Jackson Queuing Network (JQN) and feedback control are integrated to devise a container provisioning algorithm which leverages the neural networks’ ability to fit nonlinear performance models, the real-time responsiveness of feedback control, and the precise prediction of micro-service interactions offered by the JQN. The proposal is evaluated on a real Kubernetes based Cloud Native cluster. Experimental results illustrate that the container cost is decreased by 10.94%$\sim$11.36% while satifisfying Service Level Agreements (SLA) in terms of 95thaccessing-path response times.

Compared to traditional manufacturing, there are several unique characteristics in cloud manufacturing (CMfg): more candidate suppliers, more material types, more supply modes, and broader geographically distributed suppliers. These characteristics lead to a huge set of candidate supply plans with several uncertainties in logistics. It is a great challenge to effectively and efficiently select appropriate suppliers for each type of material. In this article, we consider a SSMS problem with multiuncertainties in logistics to minimize the total cost of a CMfg manufacturing enterprise. The delivery time is stochastic along with the consideration of stochastic disruption and loss in logistics. Based on state-and-transition modeling, a stochastic dynamic programming model is developed for the problem under study. By integrating proximal policy optimization (PPO) with recurrent neural network (RNN) and expectation model (EM), a stochastic optimization method PPO-REM is proposed to minimize the cost by effectively selecting suppliers and intelligently making make-or-buy decisions under uncertainties. The proposed method is evaluated by comparing to other reinforcement learning (RL) methods and existing methods for similar problems over a comprehensive set of numerical experiments with some real-world data. Experimental results show that the proposed PPO-REM converges faster with a higher reward than other RL methods, and it costs the least as compared to existing methods for similar problems.

Text-based CAPTCHA remains a widely employed scheme for distinguishing between human users and machine attackers during logging-in on systems. In this paper, we propose a reinforced perturbation generation (RPG) framework to automatically construct effective perturbation factors with reinforcement learning, and achieve a perturbed CAPTCHA that is user-friendly but challenging for machine attackers. More specifically, RPG exploits a perturbation initialization (PI) component to provide a preliminary perturbation factor. Furthermore, a perturbation reinforcement (PR) component is devised to optimize the combinations of multiple perturbation factors by a number of perturbation generation methods, which is achieved by reducing the gap between estimated cumulative rewards and real cumulative rewards. In particular, an attack model is introduced to produce the reward based on whether it can correctly recognize the perturbation CAPTCHA. The multiple perturbation factors are fused to be combined with the original CAPTCHA to against machine attackers. Extensive experiments conducted on eight real-world CAPTCHA datasets show outstanding performance against the CAPTCHA attack models.

Microservices are being used more and more in the development of cloud-based applications. Using containers, microservice instances can be made to be easier to scale and keep up to date. In order to address the necessity of guaranteeing diverse quality of service (QoS) requirements, the scheduling of microservice workflows in mobile edge computing poses a significant challenge that requires attention and resolution. In this research, a heuristic method called RWSMS is introduced, the system aims to achieve this objective while also ensuring that deadline and reliability criteria are met. This study presents a proposed scheduling strategy that incorporates RWSMS algorithms to minimize the cost of workflow execution, while simultaneously ensuring that the user-defined deadline is met and reliability is assured. Additionally, the RWSMS system incorporates a resource adjustment approach in order to optimize resource consumption. By conducting a series of comprehensive experiments using different real-world workflow applications, the effectiveness and efficiency of RWSMS are evaluated and compared with existing algorithms. The results confirm that RWSMS successfully achieves lower execution costs while meeting the required deadlines and ensuring reliability.

To fulfill their expanding computational demands, businesses are using cloud computing more and more these days. However, cloud systems alone may not always suffice. Consequently, multi-cloud systems, which provide more scalable storage and computing resources, are becoming more popular. This paper focuses on scheduling Spark workflow tasks in a multi-cloud environment. It addresses the challenges posed by different pricing models, dynamic resource provisioning, inter and intra transmission time, and the instability of resource performance. To tackle these issues, in this work, we propose a heuristic-based solution that considers factors such as VM instances, precedence constraints, transmission times, and the impact of performance uncertainty aiming to minimize rental costs while ensuring that workflow deadlines are met. The results show that the proposed method is effective in scheduling Spark workflow tasks in a multi-cloud environment while considering performance uncertainty.

Serverless applications based on microservices typically comprise dozens or hundreds of loosely coupled functions. Each request in these applications triggers a function chain, which invokes a subset of functions. However, the invocation paths may not be predetermined in dynamic function chains. In addition, there are multiple memory configurations for each function in a chain. Different memory configuration combinations bring different execution times and costs. The configuration space grows exponentially as the length of the function chain increases. Therefore, it is challenging to determine the memory configurations for functions in a dynamic function chain to minimize the execution time and cost with an uncertain invocation path and a large configuration space. In this paper, a memory configuration problem of linear dynamic function chains is investigated to minimize the cost while meeting a specified SLO (service level objective). RLMC (Reinforcement Learning-based Memory Configuration Algorithm) is adopted to make memory configuration decisions dynamically. States, actions, and rewards are specially designed for the problem under study. In addition, a punishment factor adjustment strategy is developed to accommodate different SLOs. The proposed algorithm is evaluated and compared to existing algorithms over a comprehensive set of randomly generated serverless workflow applications. Experimental results demonstrate that RLMC significantly reduces the cost of dynamic function chains while meeting SLOs and outperforms other algorithms.

These days, the usage of cloud computing services for different applications has been growing progressively. The applications, including business, commerce, healthcare, and others, require additional computation capabilities for their executions. To fulfil their expanding computational demands, cloud computing offers a pay-as-you-go billing model to run these applications cost-effectively. However, due to the complex requirements of these applications, more than one cloud system is required because single-cloud solutions are often limited by resource constraints, such as inadequate storage and computing power, as well as single-point failures that can compromise the integrity of the entire application. Consequently, multi-cloud strategies, which provide more scalable storage and computing resources, are becoming increasingly popular. However, the multi-cloud landscape consists of many cloud providers, and effectively managing workflow scheduling presents a significant hurdle in this dynamic environment. This paper focuses on scheduling Spark workflow tasks in multi-cloud networks. It addresses the challenges posed by different pricing models, dynamic resource provisioning, inter- and intra-transmission time, and the instability of resource performance. To solve these challenges, we propose a novel heuristic-based approach that considers different constraints such as VM instances heterogeneity, priority constraints, transmission times, and the impact of performance uncertainty. The goal is to schedule all tasks on virtual machines (VMs) with rental costs as low as possible while meeting workflow deadlines. The simulation results show that the proposed method effectively schedules Spark workflow tasks in multi-cloud networks, improving the scheduling performance by 50% compared to existing approaches.

Misinformation detection in short videos on social media has become a pressing issue due to its popularity. However, datasets for misinformation detection are limited in terms of modality and sources, hindering the development of effective detection methods. In this article, we introduce a novel dataset denoted the multiplatform multimodal misinformation (3M) dataset. Our dataset is collected specifically to investigate and address misinformation in a multimodal context. A total of 17 352 videos were collected from two prominent social media platforms, namely TikTok and Weibo. The 3M dataset covers 30 different topics, such as sports, health, news, and art, providing a diverse range of content for analysis. We propose a novel approach named cross-modal attention misinformation detection (CAMD) for effectively detecting and addressing multimodal misinformation. CAMD leverages the cross-modal attention module to facilitate effective information exchange and fusion between modalities by learning the correlations and weights among them. The cross-modal attention module is capable of learning multilevel modality correlations, focuses primarily on the interaction between multimodal sequences across different time steps, and simultaneously adjusts the information from the source modality based on the information of the target modality. Extensive experiments on the 3M dataset show that the proposed method achieves state-of- the-art performance. Specifically, CAMD achieves accuracy, F1-score, precision, and recall values of 76.86%, 58.05%, 87.86%, and 58.70%, respectively, on the 3M dataset.

Palmprint recognition has shown great value for biometric recognition due to its advantages of good hygiene, semi-privacy and low invasiveness. However, most existing palmprint recognition studies focus only on homogeneous palmprint recognition, where comparing palmprint images are collected under similar conditions with small domain gaps. To address the problem of matching heterogeneous palmprint images captured under the visible light (VIS) and the near-infrared (NIR) spectrum with large domain gaps, in this paper, we propose a Fourier-based feature learning network (FFLNet) for VIS-NIR heterogeneous palmprint recognition. First, we extract the multi-scale shallow representations of heterogeneous palmprint images via three vanilla convolution layers. Then, we convert the shallow palmprint feature maps into frequency-specific representations via Fourier transform to separate different layers of palmprint features, and exploit the underlying common and palmprint-specific frequency information of heterogeneous palmprint images. This effectively reduces the modality gap of heterogeneous palmprint images at the feature level. After that, we convert the common frequency-specific feature maps back to the spatial domain to learn the identity-invariant discriminative features via residual convolution for heterogeneous palmprint recognition. Extensive experimental results on three challenging heterogeneous palmprint databases clearly demonstrate the effectiveness of the proposed FFLNet for VIS-NIR heterogeneous palmprint recognition.

Social media serves as a real-time collecting and disseminating center of users’ ideas, opinions, and experiences. The deliberate disinformation and rumors propagate rapidly online due to their exaggerated facts, controversial opinions, divisive perspectives, and stunning expressions. Rumor detection approaches typically use social media posts with rumor or non-rumor labels for training and testing without disclosing the rationale behind decision-makings. On one hand, collecting evidence data to verify claims relies on expert efforts. On the other hand, verifying the truthfulness of confusing claims with distracting and lengthy evidences is still challenging. In this paper, we contribute a rumor detection dataset with multi-granularity evidences, denoted as the RD-E dataset, which includes response, fact-check, article, sourcing data and generated evidence by large language models, supporting models to verify the truthfulness of claims on social media. A number of 32,892 claims from 4,525 public individuals and organizations are annotated to 6 kinds of labels, including true, mostly true, half true, mostly false, false, pants on fire, covering a wide range of topics, e.g., politics, economy, society, technology, and health. In the experiments, seven rumor detection models have been investigated and customized on four predefined subtasks for comparisons.

It is challenging to eliminate the domain shift between seen and unseen classes in multimodal zero-shot learning tasks due to the underlying disparity between the data distributions in the seen and unseen domains. In this paper, we propose a progressive placeholder learning network with mixup hallucination and an alternating mixer, denoted as MHAM, to maintain embedding spaces for unseen classes. Utilizing mixup hallucination (MH) on the visual and textual features obtained by BERT and a vision transformer, MHAM generates visual and textual hallucinated representations with pseudo class embeddings as placeholders for the unseen classes. Furthermore, a number of alternating mixer (AM) blocks are stacked to obtain modality-shared representations for the seen classes and hallucinated representations of progressive placeholders for the unseen classes. In particular, modality-shared representations are obtained by a mixer in an AM block by reversing the dimensionality of the modality-specific and raw representations to model intermodal interactions. MHAM exploits a freezing strategy by fixing the weights over the unseen classes in the last fully connected layer; this step acts as a projection from the raw and modality-shared representations to the embedding space of the seen and unseen classes. Experiments conducted on zero-shot datasets and news event datasets demonstrate the superior performance of the proposed MHAM method.

Serverless functions (SFs) and on-demand virtual machines (VMs) are common cloud resources for scientific workflow applications, which are widespread in many fields. SFs are paid by actual running time with higher unit costs and higher resource utilization than VMs which are paid by billing time units. Generally, each application is executed on a limited budget. In this article, we study the challenging cloud workflow scheduling problem with a limited budget to minimize makespan in a hybridization of SFs and on-demand VMs for which the BCWS (Budget Constrained Workflow Scheduling) algorithm is proposed. Methods are developed to determine the task execution order, rent cloud resources and map tasks to resources respectively. Together with initial schedule construction and schedule improvement policies, these procedures are repeatedly applied in BCWS. The proposed algorithm is evaluated by comparing it to existing algorithms for similar problems over a comprehensive set of workflow instances. Experimental results show that the proposed algorithm significantly reduces the makespan with a hybrid configuration of VMs and SFs compared to the server only or the serverless only configurations and outperforms the compared algorithms which are the best existing ones for similar problems.

In MEC, many deadline-constrained real-time work-flows with computation-intensive and/or delay-sensitive tasks are common in intelligent mobile devices (MDs). Though a task can be executed by either the local MD or an MEC server, the tasks of each work-flow are constrained by complex precedences, and real-time task offloading is somewhat tricky. In this paper, we consider the task offloading problem for stochastic work-flows with soft deadline constraints to minimize total tardiness and proposed an online RL-based offloading algorithm. In the algorithm, realtime tasks are dynamically partitioned into partial precedences in terms of which real-time RL states are constructed. Adaptive offloading actions are developed to determine task execution sequences for different states to optimize total tardiness. Experimental results show that the proposed online offloading algorithm outperforms the compared ones.

Social media allows the public to access information conveniently, in which the false messages that are eye-catching may spread fast. In this paper, we propose a two-stage confidence-guided boundary adaption (CBA) network, consisting of a feature preprocessing (FP) module, a biased ambiguity learning (BA) module and a confidence-guided boundary adaptation (CG) module. In the first stage, the FP module obtains the textual and visual features, which are fused by conducting the visual-to-textual and textual-to-visual correlation coefficients with attention mechanism. Furthermore, BA evaluates the distribution distance between fused features and single modalities to determine the weights between modalities, capturing the semantics of key modality. In the second stage, CG leverages samples from the low-confidence interval to generate new instances using a mixup of augmentation techniques, aiming to occupy the decision space and optimize the decision boundary of the classifier. Extensive experiments on two public datasets show that our CBA model is 1.6% and 2.6% higher than the state-of-the-art methods.

Feature selection (FS) for classification is crucial for large-scale images and bio-microarray data using machine learning. It is challenging to select informative features from high-dimensional data which generally contains many irrelevant and redundant features. These features often impede classifier performance and misdirect classification tasks. In this article, we present an efficient FS algorithm to improve classification accuracy by taking into account both the relevance of the features and the pairwise features correlation in regard to class labels. Based on conditional mutual information and entropy, a new supervised similarity measure is proposed. The supervised similarity measure is connected with feature redundancy minimization evaluation and then combined with feature relevance maximization evaluation. A new criterion max-relevance and min-supervised-redundancy (MRMSR) is introduced and theoretically proved for FS. The proposed MRMSR-based method is compared to seven existing FS approaches on several frequently studied public benchmark datasets. Experimental results demonstrate that the proposal is more effective at selecting informative features and results in better competitive classification performance.

With an increasing complexity and functionality in cloud data centers, fault tolerance becomes an essential requirement for tasks executed in clouds, especially for workflows with task precedences. Hosts and network devices are the main physical components in a cloud data center. The PB (Primary-Backup) model is a desirable approach to fault tolerance. Many PB-based workflow scheduling algorithms have been proposed for host faults. However, only a few studies focus on cloud workflow scheduling considering network device faults. This paper analyzes the fault-tolerant properties for scheduling dependent tasks and migrating VMs based on the PB model, considering both host and network device faults in a cloud data center. A failure-aware elastic cloud workflow scheduling algorithm is designed for both host and network device fault tolerance. Additionally, an elastic resource provisioning mechanism is proposed and incorporated into the proposed algorithm to improve resource utilization. Performance evaluations on both randomly generated and real-world workflows show that the proposal effectively improves resource utilization while guaranteeing fault tolerance.

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 Internet of Things (IoT)-enabled applications use sensors and actuators to collect big data, which are processed by big data models, e.g., Spark. Generally, data processing tasks are precedence constrained and the computation results are transmitted to other IoT devices. In this article, we consider the Spark workflow problem of scheduling tasks with data affinity to heterogeneous servers to minimize the maximum completion time. In a Spark instance, jobs are precedence constrained and stages for each job are also precedence constrained. There are a large number of topological stage orders. A balance between task execution times, determined by heterogeneous servers, and transmission times caused by data affinity is difficult to achieve. A scheduling optimization algorithm framework is proposed, which consists of five components: 1) temporal parameter calculation; 2) ready stage adding; 3) task sequencing; 4) resource allocation; and 5) schedule improvement. Strategies for each component are developed. The algorithmic components are statistically calibrated over a comprehensive set of instances. The proposed algorithm is compared to two modified classic algorithms for similar problems on typical scientific workflow instances. The experimental results demonstrate the effectiveness of the proposal for the considered problem.

Feature selection is important in both machine learning and pattern recognition. Successfully selecting informative features can significantly increase learning accuracy and improve result comprehensibility. Various methods have been proposed to identify informative features from high-dimensional data by removing redundant and irrelevant features to improve classification accuracy. In this article, we systematically survey existing sparse learning models for feature selection from the perspectives of individual sparse feature selection and group sparse feature selection, and analyze the differences and connections among various sparse learning models. Promising research directions and topics on sparse learning models are analyzed.

Many practical multiobjective optimization problems have a nested bilevel structure in variables, which can be modeled as bilevel multiobjective optimization problems (BLMOPs). In this article, a cooperative coevolution (CC) with knowledge-based variable decomposition, called bilevel multiobjective CC (BLMOCC), is proposed for BLMOPs. In BLMOCC, the variable interactions are represented by an interaction matrix. The perturbation-based variable decomposition combined with the matrix completion approach has been designed for dynamically discovering the correlation among the bilevel variables, based on which the variables are divided into different groups. To further handle possible weak correlations among various groups of variables, a CC has been adopted for optimizing them in a collaborative way. In experimental studies, BLMOCC is compared with a nested method (NS) and a state-of-the-art algorithm (H-BLEMO) on a set of benchmark problems. The effects of each component in BLMOCC have also been verified by comparing it with its three variants. The experimental results demonstrate that BLMOCC has the best performance among all the compared algorithms. In addition, BLMOCC has also been applied to a real-world management decision-making problem, which further validates its efficiency and effectiveness.

Performance analysis and optimization is a critical task for the successful development of cloud computing systems and services. Unfortunately, performance analysis and optimization remains complicated and challenging due to several unique characteristics in cloud computing such as stochastic service requests, request sequencing strategies, and request distribution methods. In this paper, we present a comprehensive survey on the performance analysis and optimization for stochastic cloud service requests. By analyzing the main entities and activities in the common routines of performance analysis, we first propose a generic performance analysis framework, which contains five fundamental characteristics: Request, Sequencing, Queue, Distribution and Services. Practical factors of each characteristic are analyzed. We discuss the effects of each characteristic of the framework on optimization objectives including cost, profit, response time, and energy consumption. We then systematically review and compare 13 representative queuing models using the proposed framework. Based on the practical factors of the five characteristics and along with the current research efforts, we also identify several research opportunities and challenges.

In this article, we consider the dynamic allocation of bursty requests stochastically arriving at heterogeneous servers with uncertain setup times. Lower expected response time and less power consumption are desirable objectives of users and service providers respectively. However, sudden increase and decrease of cloud servers caused by bursty requests are rather challenging to get an appropriate trade-off between the two conflicting objectives which are closely related to the launched servers. The heterogeneity of the cloud servers further makes it more difficult to decide how to switch on and off servers and effectively and efficiently allocate bursty requests with balanced objectives. Based on a Markov decision process, a real-time bilevel decision-making model is constructed for unallocated requests which includes: whether to launch a server and which type of server to launch. A learn-and-deploy algorithm framework is proposed which contains two complementary stages. In the first stage, an effective offline bi-objective optimization algorithm is proposed to learn a set of policies, which provides helpful trade-off information for a decision-maker to choose a preferred policya posteriori. In terms of the system status, a policy decides whether to launch a server according to a state-action table and which server to launch using a server priority sequence. In the second stage, a computationally efficient policy deployment method is proposed to search the corresponding action in the selected policy based on the current system status and apply it to the real-time system. Experimental studies over a large number of random and real instances have been conducted to validate the effectiveness of the proposed bilevel model and algorithm. Compared to the most recent existing method, the performance of the proposed approach can at most achieve an 80% improvement on power consumption and 20% improvement on response time.

Functions provided by Web applications are increasingly diverse which make their structures complicated and meshed. Cloud computing platforms provide elastic computing capacities for these meshed Web systems to guarantee Service Level Agreement (SLA). Though workloads of meshed Web systems usually change steadily and periodically in total, sometimes there are sudden fluctuations. In this paper, a hybrid State-space-model-and-Queuing-network based Feedback control method (SQF) is developed for auto-scaling Virtual Machines (VMs) allocated to each tier of meshed Web systems. For the case with workloads changing steadily, a State-space-model based static Feedback Control method (SFC) is proposed in SQF to stabilize request response times near the reference time. For unsteadily changing workloads, a Queuing-network based multi-tier collaborative Feedback Control method (QFC) is proposed for effectively eliminating bottlenecks. QFC builds a control system for each tier individually and uses the queuing network to measure the interaction relationships among different tiers. Experimental results show that QFC is able to improve the efficiency of eliminating bottlenecks (decreasing upper-limit SLA violation ratios by 31.99%$\sim$56.52%) with similar or a little bit high VM rental costs compared to existing methods while SFC obtains more stable response times for requests with reasonable additional costs.

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.

Nowadays, energy costs are the most important factor in cloud computing. Therefore, the implementation of energy-aware task scheduling methods is of utmost importance. A task scheduling framework considering deadlines, data locality and resource utilization is proposed to save on energy costs in heterogeneous clusters. The framework consists of task list construction, task scheduling and slot list updating. In terms of deadline constraints, number of job slots allocated and possible processing times of jobs, a new job sequence is proposed to construct an reasonable task list. Tasks are scheduled to promising slots from their rack-local servers, cluster-local servers and remote servers in the produced task scheduling, which greatly improves data locality. After the assignment among tasks and slots, an update of available slots in clusters is proposed not only to find available slots but also to improve server resource utilization using fuzzy logic with the available number of slots according to current CPU, memory and bandwidth utilization. Experimental results show that the proposed heuristic results in lower energy consumption than the adapted existing algorithms with a variable total number of slots.

Among multiple fault-tolerant strategies, resubmission, and replication are fundamental and widely recognized in distributed computing systems. In recent years, many algorithms based on replication or resubmission have been proposed. However, few of them consider these two techniques together, especially in Cloud systems. In this article, we propose a Hybrid Fault-Tolerant Scheduling Algorithm (HFTSA) for independent tasks with deadlines by integrating the above techniques in virtualized Cloud systems. During the task scheduling process, HFTSA selects fault-tolerant strategies from resubmission and replication for each accepted task based on the characteristics of both task and Cloud resources and then reserves suitable resources. During the task execution process, HFTSA adopts an online adjustment scheme for fault-tolerant strategies of some tasks if necessary while providing an online scheduling scheme for faults. Moreover, an elastic resource provisioning mechanism is designed and incorporated into HFTSA to dynamically adjust the provided resources to improve resource utilization. Experiments on a real cloud platform and a simulated platform are conducted to verify the effectiveness of the proposed HFTSA. The results demonstrate that HFTSA can provide an efficient fault-tolerant scheduling strategy for deadline-constrained tasks with high resource utilization and performs better than corresponding competitors.

Though microservices process and communicate with lightweight mechanisms, finer tasks result in much more complicated precedence constraints. Different tasks have distinct resource requirements and different VMs (Virtual Machine) have various configurations and prices. In this paper, we consider the problem of scheduling microservice tasks of workflow applications to containers configured on on-demand VMs to minimize the total rental cost. The problem is mathematically modelled using integer programming and an algorithm framework is proposed. For dynamic available containers and resource requirements, a task scheduling heuristic is presented for scheduling precedence-constrained or independent tasks to available containers. All parameters and components of the proposed algorithm framework are statistically calibrated by the Analysis of Variance technique on a large number of random instances. Performance of the the proposed algorithm is verified over a lot of instances.

The maximization of the Quality of Service (QoS) for multi-tenants is one of the key issues for cloud-edge service providers. Limited computing resources, different priorities, and deadlines of tenants make it difficult to satisfy the demands of all the multi-tenants. This paper considers the problem of scheduling limited cloud-edge resources to multi-tenant workflow applications with priority and deadline constraints. A level-based iterative greedy algorithm for the problem is proposed. The algorithm defines a priority-based multi-tenant instance success entropy to measure the total quality of service. The destruction & reconstruction and local search of the algorithm is performed based on the level of tasks. The proposed algorithm is compared to modified classical algorithms for similar problems. Experimental results demonstrate the effectiveness of the proposal for the considered problem.

Task scheduling with multi-dimensional configuration requirements is widely used in cloud platforms such as OpenStack and Kubernetes. In this paper, we consider the problem of scheduling tasks with multi-dimensional configuration to hybrid resources. An energy-aware scheduling algorithm on tasks with multi-dimensional configuration requirements (ESMCR in short) is presented. ESMCR is combined with a decomposition-based multi-objective evolutionary algorithm to minimize energy consumption and provide sufficient capacity for the data center. An entropy-based performance index is modeled to measure the QoS. The experimental results indicate that the proposed algorithms outperform the compared algorithms significantly.

In cloud computing, reserved and on-demand instances are generally provided by service providers. Hybridization of the two alternatives can considerably save costs when renting resources from the cloud. However, it is a big challenge to determine the appropriate amount of reserved and on-demand resources in terms of users’ requirements. In this paper, the workflow scheduling problem with both reserved and on-demand instances is considered. The objective is to minimize the total rental cost under deadline constrains. The considered problem is mathematically modeled. A multiple sequence-based earliest finish time method is proposed to construct schedules for the workflows. Four different rules are used to generate initial task allocation sequences. Types and quantities of resources are determined by a free time block-based schedule construction mechanism. New sequences are generated by a variable neighborhood search method. Experimental and statistical analyses and results demonstrate that the proposed algorithm algorithm generates considerable cost savings when compared to the algorithms with only on-demand or reserved instances.

The gate assignment problem (GAP) aims at assigning gates to aircraft considering operational efficiency of airport and satisfaction of passengers. Unlike the existing works, we model the GAP as a bi-objective constrained optimization problem. The total walking distance of passengers and the total robust cost of the gate assignment are the two objectives to be optimized, while satisfying the constraints regarding the limited number of flights assigned to apron, as well as three types of compatibility. A set of real instances is then constructed based on the data obtained from the Baiyun airport (CAN) in Guangzhou, China. A two-phase large neighborhood search (2PLNS) is proposed, which accommodates a greedy and stochastic strategy (GSS) for the large neighborhood search; both to speed up its convergence and to avoid local optima. The empirical analysis and results on both the synthetic instances and the constructed real-world instances show a better performance for the proposed 2PLNS as compared to many state-of-the-art algorithms in literature. An efficient way of choosing the tradeoff from a large number of nondominated solutions is also discussed in this article.

Assessing the performance of Pareto front (PF) approximations is a key issue in the field of evolutionary multi/many-objective optimization. Inverted generational distance (IGD) has been widely accepted as a performance indicator for evaluating the comprehensive quality for a PF approximation. However, IGD usually becomes infeasible when facing a real-world optimization problem as it needs to know the true PF a priori. In addition, the time complexity of IGD grows quadratically with the size of the solution/reference set. To address the aforementioned issues, a grid-based IGD (Grid-IGD) is proposed to estimate both convergence and diversity of PF approximations for multi/many-objective optimization. In Grid-IGD, a set of reference points is generated by estimating PFs of the problem in question, based on the representative nondominated solutions of all the approximations in a grid environment. To reduce the time complexity, Grid-IGD only considers the closest solution within the grid neighborhood in the approximation for every reference point. Grid-IGD also possesses other desirable properties, such as Pareto compliance, immunity to dominated/duplicate solutions, and no need of normalization. In the experimental studies, Grid-IGD is verified on both the artificial and real PF approximations obtained by five many-objective optimizers. Effects of the grid specification on the behavior of Grid-IGD are also discussed in detail theoretically and experimentally.

In cloud computing, service providers rent heterogeneous servers from cloud providers, i.e., Infrastructure as a Service (IaaS), to meet requests of consumers. The heterogeneity of servers and impatience of consumers pose great challenges to service providers for profit maximization. In this article, we transform this problem into a multi-queue model where the optimal expected response time of each queue is theoretically analyzed. A multi-queue request scheduling algorithm framework is proposed to maximize the total profit of service providers, which consists of three components: request stream splitting, requests allocation, and server assignment. A request stream splitting algorithm is designed to split the arriving requests to minimize the response time in the multi-queue system. An allocation algorithm, which adopts a one-step improvement strategy, is developed to further optimize the response time of the requests. Furthermore, an algorithm is developed to determine the appropriate number of required servers of each queue. After statistically calibrating parameters and algorithm components over a comprehensive set of random instances, the proposed algorithms are compared with the state-of-the-art over both simulated and real-world instances. The results indicate that the proposed multi-queue request scheduling algorithm outperforms the other algorithms with acceptable computational time.

In this paper, we consider single-machine group scheduling with nonperiodical maintenance and deteriorating effects. Nonperiodical maintenance, which has unfixed maintaining interval or the number of jobs in each group is unfixed, results in a variable number of groups. Deteriorating effects lead to longer processing times of which the deterioration index depends on job grouping. This problem is of significance in different production settings and is much more difficult than and general that other simpler single-machine group scheduling problems. Making use of historical processing times, we construct the actual processing time model for jobs. We prove that the problem under study is NP-hard. By transforming the optimization objective, properties are discovered and two batch-based heuristics are presented for small size problems. To further improve the effectiveness for large size problems, an iterated greedy algorithm is proposed being its main advantages simplicity and effectiveness. The proposed methods are evaluated over a large number of random instances with calibrated parameters and components. Comprehensive computational and statistical analyses demonstrate the superiority of the methods proposed over adapted existing approaches.

Metadata in most existing building automation systems (BASs) is inconsistent, incomplete, and nondescriptive. This situation is a major obstacle to the widespread use of data analytics to improve the operation of buildings. In this article, we put forward a method to infer zone-level metadata from features derived from BAS data. The method includes two steps: 1) classification of BAS points into different types (e.g., indoor temperature, indoor temperature set point, airflow, airflow set point, damper position, and radiator valve position) and 2) association of BAS points based on their functional relationships (i.e., grouping the sensors, actuators, and set points of each zone together). The metadata inference method was demonstrated with data from zones served by four different air handling units (AHUs) in two office buildings in Ottawa, ON, Canada. The results from this case study indicate that common zone-level BAS point types can be accurately classified and associated even in the absence of intuitive data labels. Note to Practitioners-This article was motivated by the problem of metadata normalization in existing buildings, in order to scale up the application of smart building solutions in the real world. Existing metadata normalization approaches mainly focused on inferring the point types of the metadata with both semantic (label) and numerical information (time series readings). In this article, we put forward a method to infer zone-level metadata with numerical information only. Methods for both types of classification and relationships' association of the BAS points are investigated. The results from two office buildings indicate that the classification phase can achieve an average of 90% accuracy, while the association phase can obtain an average of 85% accuracy. The method was developed and demonstrated with a limited data set by using data exclusively from zone-level sensors, actuators, and set points. Future work is planned to extend the proposed method to more comprehensive BAS data sets with the system- and plant-level data as well.

In this article, we consider the problem of selecting appropriate heterogeneous servers in cloud centers for stochastically arriving requests in order to obtain an optimal tradeoff between the expected response time and power consumption. Heterogeneous servers with uncertain setup times are far more common than homogenous ones. The heterogeneity of servers and stochastic requests pose great challenges in relation to the tradeoff between the two conflicting objectives. Using the Markov decision process, the expected response time of requests is analyzed in terms of a given number of available candidate servers. For a given system availability, a binary search method is presented to determine the number of servers selected from the candidates. An iterative improvement method is proposed to determine the best servers to select for the considered objectives. After evaluating the performance of the system parameters on the performance of algorithms using the analysis of variance, the proposed algorithm and three of its variants are compared over a large number of random and real instances. The results indicate that proposed algorithm is much more effective than the other four algorithms within acceptable CPU times.

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.

Cloud computing is a new resource provisioning mechanism, which represents a convenient way for users to access different computing resources. Periodical workflow applications commonly exist in scientific and business analysis, among many other fields. One of the most challenging problems is to determine the right amount of resources for multiple periodical workflow applications. In this paper, the periodical workflow applications scheduling problem with total renting cost minimization is considered. The novelty of this work relies precisely on this objective function, which is more realistic in practice than the more commonly considered makespan minimization. An integer programming model is constructed for the problem under study. A Precedence Tree based Heuristic (PTH) is developed which considers three types of initial schedule construction methods. Based on the initial schedule, two improvement procedures are presented. The proposed methods are compared with existing algorithms for the related makespan based multiple workflow scheduling problem. Experimental and statistical results demonstrate the effectiveness and efficiency of the proposed algorithm.

In this paper, we consider the cost minimization problem for scheduling stochastic service requests to heterogenous servers in cloud computing. Service requests are impatient with different maximizing waiting time. Using queuing theory, a queuing system model is constructed. An algorithm framework is proposed to minimize the cost. The actual expected waiting time of service requests is analyzed. The rejection probability of the system is obtained. Comparing the rejection probability of the system to a given system availability, suitable servers are selected to minimize the cost. Based on the proposed framework, algorithms with different components are compared. Experimental results show that the algorithm with the mixed server selection strategy outperforms the others on efficiency.

Feature selection plays an important role in big data mining and pattern recognition, which includes selecting a subset of the most informative features that produces compatible results as the original entire set of features. A new similarity measure is proposed in terms of information theory, in particular joint mutual information between features with respect to class labels. Based on the similarity measure, an adaptive spectral clustering that could determine cluster number adaptively is proposed. Furthermore, we propose a new feature selection algorithm called Adaptive Spectral Clustering based on Joint Mutual Information (ASC-JMI) which can effectively and efficiently deal with both irrelevant and redundant features, and select a high-quality feature subset. The experimental results on five high-dimensional benchmark datasets demonstrate that the ASC-JMI is effective in selecting the informative features and obtains competitive classification performance.

To meet the dynamic workload requirements in widespread task-batch based workflow applications, it is important to design algorithms for DAG-based platforms (such as Dryad, Spark and Pegasus) to rent virtual machines from public clouds dynamically. In terms of depths and functionalities, tasks of different task-batches are merged into task-units. A unit-aware deadline division method is investigated for properly dividing workflow deadlines to task deadlines so as to minimize the utilization of rented intervals. A rule-based task scheduling method is presented for allocating tasks to time slots of rented Virtual Machines (VMs) with a task right shifting operation and a weighted priority composite rule. A Unit-aware Rule-based Heuristic (URH) is proposed for elastically provisioning VMs to task-batch based workflows to minimize the rental cost in DAG-based cloud platforms. Effectiveness of the proposed URH methods is verified by comparing them against two adapted existing algorithms for similar problems on some realistic workflows.

Relevant gene selection is crucial for analyzing cancer gene expression datasets including two types of tumors in cancer classification. Intrinsic interactions among selected genes cannot be fully identified by most existing gene selection methods. In this paper, we propose a weighted general group lasso (WGGL) model to select cancer genes in groups. A gene grouping heuristic method is presented based on weighted gene co-expression network analysis. To determine the importance of genes and groups, a method for calculating gene and group weights is presented in terms of joint mutual information. To implement the complex calculation process of WGGL, a gene selection algorithm is developed. Experimental results on both random and three cancer gene expression datasets demonstrate that the proposed model achieves better classification performance than two existing state-of-the-art gene selection methods.

The bi-objective shortest path problem exists in many practical applications with complex networks. It is much time-consuming for searching all non-dominated solutions, especially for large size problems. However, only a small number of them are crucial for users' decision making. In this paper, the Pareto front is segmented by grids. The grids are determined according to the two requirements given by users. Non-dominated solutions are assumed to be similar and any of them meets the user's requirements, i.e., finding only one solution is necessary for each grid. A fast algorithm is proposed for finding the bi-objective shortest path in such user-driven problems. Experimental results illustrate the efficiency and effectiveness of the proposed algorithm.

No-wait flowshop scheduling problems are widespread in industries. Though processing times of jobs are traditionally assumed to be constant, they are variable because of learning and deteriorating effects in practical manufacturing processes which make the problems much more difficult. In this paper, we propose a metaheuristic, self-adaptive memetic algorithm (SAMA for short), for no-wait flowshops with variable processing times which have never been considered yet. The balance between intensification and diversification of the algorithm is adaptively controlled by evolutionary operators. Local search is performed on better individuals with higher probabilities to dynamically adjust diversification. Experimental results show that the proposed SAMA outperforms existing algorithms for similar problems.

The mixed no-wait flowshop problem with both wait and no-wait constraints has many potential real-life applications. The problem can be regarded as a generalization of the traditional permutation flowshop and the no-wait flowshop. In this paper, we study, for the first time, this scheduling setting with makespan minimization. We first propose a mathematical model and then we design a speed-up makespan calculation procedure. By introducing a varying number of destructed jobs, a modified iterated greedy algorithm is proposed for the considered problem which consists of four components: 1) initialization solution construction; 2) destruction; 3) reconstruction; and 4) local search. To further improve the intensification and efficiency of the proposal, insertion is performed on some neighbor jobs of the best position in a sequence during the initialization, solution construction, and reconstruction phases. After calibrating parameters and components, the proposal is compared with five existing algorithms for similar problems on adapted Taillard benchmark instances. Experimental results show that the proposal always obtains the best performance among the compared methods.

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.

Allocating service capacities in cloud computing is based on the assumption that they are unlimited and can be used at any time. However, available service capacities change with workload and cannot satisfy users' requests at any time from the cloud provider's perspective because cloud services can be shared by multiple tasks. Cloud service providers provide available time slots for new user's requests based on available capacities. In this paper, we consider workflow scheduling with deadline and time slot availability in cloud computing. An iterated heuristic framework is presented for the problem under study which mainly consists of initial solution construction, improvement, and perturbation. Three initial solution construction strategies, two greedy- and fair-based improvement strategies and a perturbation strategy are proposed. Different strategies in the three phases result in several heuristics. Experimental results show that different initial solution and improvement strategies have different effects on solution qualities.

Workers with different levels of experience and knowledge have different effects on job processing times. By taking into account 1) the sum-of-processing-time; 2) the job-position; and 3) the experience of workers, a more general learning model is introduced for scheduling problems. We show that this model generalizes existing ones and brings the consideration of learning and forgetting effects closer to reality. We demonstrate that some single machine scheduling problems are polynomially solvable under this general model. Considering the forgetting effect caused by the idle time on the second machine, we construct a learning-forgetting model for the two-machine permutation flow shop scheduling problem with makespan minimization. A branch-and-bound method and four heuristics are presented to find optimal and approximate solutions, respectively. The proposed heuristics are evaluated over a large number of randomly generated instances. Experimental results show that the proposed heuristics are effective and efficient.

Cloud computing enables users to access different resources conveniently based on the `pay-as-you-go' model. However, the unit cost of these on-demand instances are usually high. The spot instances provide a dynamic and cheaper manner for renting resources from the cloud. However, failures are often occurred due to the fluctuations of the price of the spot instance. It is a big challenge to determine the appropriate amounts of spot and on-demand resources in terms of users' requirements. In this paper, the workflow scheduling problem with both spot and on-demand instances is considered. The objective is to minimize the total renting cost under deadline constrains. An idle time block-based method is proposed to construct schedules for workflow applications. Schedules are improved by a forward and backward moving mechanism. Experimental and statistical results demonstrate the effectiveness of the proposed algorithm over a lot of tests with different sizes.

The emergence of MapReduce, a simple software framework, is helping to deal with vast amount of data (multiterabyte data-sets) in-parallel on large clusters (thousands of nodes) of commodity hardware in a reliable, fault-tolerant manner. Extensive researches and popularity are gained by MapReduce recently. In this paper, we consider the MapReduce task scheduling problem with security and outage constraints, which are performance effected and not well resolved. The objective is to minimize the makespan while meet data locality and security requirement. A heuristic algorithm with three components is proposed for the problem under study. The simulated results verified the effectiveness of the proposed method, which is closely dependent on the outage probability and the number of worker nodes.

In cloud environments, trust is necessary because services have the characteristics of uncertainty, dynamic, false or fraudulent which usually make users difficult to obtain desired services. In this paper, we consider trust-oriented workflow scheduling with temporal constraints including service setup times and workflow deadlines. The considered problem is mathematically modeled. A behavior-based trust model is established to assess trusts of services. An iterative adjustment heuristic framework is proposed which consists of initial solution construction, solution sets generation and adjustment. Three heuristic algorithms are developed and compared with the best existing methods for similar workflow scheduling problems. Experimental results demonstrate effectiveness of the proposal.

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.

Many workflow applications are moved to clouds for elastic capacities. Elastic resource provisioning is one of the most important problems. Realistic factors are involved, including an interval-based charging model, data transfer time, VM loading time, software setup time, resource utilization, and the workflow deadline. A multirule-based heuristic is proposed for the problem under study which contains two components: a deadline division and task scheduling. Taking into account the gaps between tasks, the impact of different critical paths and the precedence constraints, the workflow deadline is properly divided into task deadlines based on the solution of a relaxed problem. The relaxed problem is modeled by integer programming and solved by CPLEX. All tasks are sorted in terms of the developed depth-based rule. For different realistic factors, three priority rules are developed to allocate tasks to appropriate available time slots, from which a weighted rule is constructed for task scheduling. The weights are calibrated by random instances. Experiments are conducted using a benchmark realistic workflow. Experimental results show that the proposal is effective and efficient for realistic workflows.

The shortest path problems (SPPs) with learning effects (SPLEs) have many potential and interesting applications. However, at the same time they are very complex and have not been studied much in the literature. In this paper, we show that learning effects make SPLEs completely different from SPPs. An adapted A* (AA*) is proposed for the SPLE problem under study. Though global optimality implies local optimality in SPPs, it is not the case for SPLEs. As all subpaths of potential shortest solution paths need to be stored during the search process, a search graph is adopted by AA* rather than a search tree used by A*. Admissibility of AA* is proven. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated.

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.

Cloud computing enables users to access different resources conveniently based on the "pay-as-you-go" model. However, the unit cost of this on-demand manner are usually higher than the reserved ones. Reallocating some high-usage on-demand instances to reserved instances can save considerable costs when renting resources from the cloud. It is a big challenge to determine the appropriate amount of reserved and on-demand instances in terms of users' requirements. In this paper, we consider deadline constrained workflow scheduling problems to minimize total renting costs with both reserved and on-demand instances. An integer programming model is constructed for the problem under study. A Precedence Tree based Heuristic (PTH) is developed which includes a dynamic initial schedule construction methods. Based on the initial schedule, an improvement procedure is presented. The proposed methods are compared with existing algorithms for the related makespan based workflow scheduling problem. Experimental and statistical results demonstrate the effectiveness and efficiency of the proposed algorithm.

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 XaaS clouds, resources as services (e.g., infrastructure, platform and software as a service) are sold to applications such as scientific and big data analysis workflows. Candidate services with various configurations (CPU type, memory size, number of machines and so on) for the same task may have different execution time and cost. Further, some services are priced rented by intervals that be shared among tasks of the same workflow to save service rental cost. Establishing a task-mode (service) mapping (to get a balance between time and cost) and tabling tasks on rented service instances are crucial for minimizing the client-oriented cost to rent services for the whole workflow. In this paper, a multiple complete critical-path based heuristic (CPIS) is developed for the task-mode mapping problem. A list based heuristic (LHCM) concerning the task processing cost and task-slot matching is developed for tabling tasks on service instances based on the result of task-mode mapping. Then, the effectiveness of the proposed CPIS is compared with that of the previously proposed CPIL, the existing state-of-the-art heuristics including PCP, SC-PCP ( an extension to PCP), DET, and CPLEX. The effectiveness of the proposed LHCM is evaluated with its use with different task-mode mapping algorithms. Experimental results show that the proposed heuristics can reduce 24 percent of the service renting cost than the compared algorithms on the test benchmarks at most for non-shareable services. In addition, half of the service renting cost could be saved when LHCM is applied to consolidate tasks on rented service instances.

In cloud computing, services are unlimited and available at any time from the perspective of users or tenants. However, the remaining service capability could not satisfy tenants' requirements at any time from the perspective of service providers because the services are shared by multiple tasks. In this paper, we consider the workflow scheduling with both deadline and time slots constraints in cloud computing. An iterated heuristic framework is investigated, which mainly consists of three phases: the initial solution generation, improvement, reconstruction. Two constructive initial solution strategies, two improving methods and an reconstruction algorithm are proposed for the three phases, respectively. These strategies combine four heuristics, which are evaluated on a lot of test-bed instances.

Deteriorating effect is critical for the processing time of a job in group scheduling for complex products, which is caused by the maintenance or repairing of machines. In this paper, we construct a time-dependent deteriorating effect model for the single-machine group scheduling problem with makespan minimization. The problem is proved to be NP-hard in strong sense. A fast makespan calculating method is derived from the analysis on properties for the considered problem. Based on a special grouping strategy, a heuristic and an enumerative method are proposed. The proposed algorithms are compared on a lot of small size instances, along with the statistical analysis on the experimental results by the Analysis of Variance.

Energy consumption in data center is gradually exceeding other operating expenditures. It is imperative to enhance the energy efficiency of data center. In this paper, two heuristics on AIS (All-In Strategy) - TSA (Task Scheduling on AIS) and TSAGT (Task Scheduling on AIS of Global Tasks) are constructed based on job performance, data locality and resource utilization for energy-aware task scheduling. Priority queue is obtained according to the number of allocated slots of jobs within deadline. Resource utilization and data locality are considered for task scheduling. Task adjusting for minimizing the completion time of cluster was proposed, which assigns the task to the server with the remaining running time similar to its processing time. Experimental results show that, the performance of TSA and TSAGT are better than existing algorithms on the completion time of cluster. Specially, TSA outperforms TSAGT in effectiveness with less completion time and TSAGT has less cost than TSA.

This paper considers the flowline manufacturing cell scheduling problem(FMCSP) with sequence dependent family setup times(SDFSTs) for makespan minimization. Based on the characteristics of this problem, hybrid harmony search (HHS) is proposed. It uses iterative optimizing algorithm to enhance the quality of the solution and applies a simple discarding strategy to avoid the algorithm converging quickly. HHS is compared with a classical heuristic algorithm and some state-of the-art meta-heuristic algorithms, which are existing algorithms for the considered problem on 900 instances. Experimental results show that HHS is the best among these algorithms in effectiveness. Thus, the proposed algorithm can be applied to FMCSP with SDFSTs in practice.

Integrates learning effects with different position-dependent learning impact factors and deteriorating effects, a general model is developed in this paper. We prove that the single-machine scheduling problems with the developed model are optimally solvable in polynomial time for optimizing makespan, total completion time and the sum of (square) completion times. Those to minimize the total weighted completion time and the maximum lateness are proved to be optimally solvable in polynomial time only for certain assumptions. Optimal solutions are demonstrated by an example for the considered problems using the constructed optimal rules.

Cloud manufacturing aims to perform large-scale collaboration for complex manufacturing by sharing distributed manufacturing resources. Resource representation is a prerequisite for achieving resource optimal allocation and it determines the robustness of cloud manufacturing systems. In this paper, a three-level modeling framework is constructed for semantically representing resource-related information and knowledge. Heterogeneous resource information is represented by the resource model level, functional features that support manufacturing resources to resolve manufacturing problems is described by the capability model level, and semantics of capability models are elaborated and exhibited from multi-granularity perspectives by the semantic-based meta-model level. A practical multi-spindle lathe case is adopted to demonstrate how the constructed framework represents cloud manufacturing resources from the semantic view, which is the foundation of resource discovery in cloud manufacturing systems.

In this paper, the multi-mode resource-constrained project scheduling problem (MRCPSP) is considered for makespan minimization, which leads to even utilization of machine capacity. According to the characteristics of the considered problem, a discrete particle swarm optimization (DPSO) is adapted, based on which a cooperative optimization method with multiple discrete particle swarms (CPSO) is proposed for MRCPSP. Two swarms are distinctively adopted to the mode assignment and activity sequencing sub-problem. Once a mode list and an activity list are obtained, the two swarms cooperatively search for better solutions. In other words, one swarm updates the mode list in terms of the given activity list and the activity list is improved by the updated mode list by the other swarm. As the same time, a local search procedure is investigated to balance the exploration and exploitation. Computation results of Project Scheduling Problem Library (PSPLIB) sets show CPSO is efficient to solve complicated combination optimization problems.

In this paper, the manufacturing process in iron and steel manufacturing systems is modeled as the m-machine no-wait flowshop scheduling problem with sequence-dependent setup times. To avoid extreme uneven utilization of machine capacity, makespan is considered as the minimization criterion. An adaptive intelligent method named GEIM is proposed, which is a new meta-heuristic on the basis of greedy randomized adaptive search procedure and evolutionary local search, for the considered problem. Path-relinking strategy is adopted to bridge the local optimum and elite solutions for exploring the solution spaces. Attributes of elite solutions are extracted to guide the local search process and an adaptive control mechanism is provided for the diversification of elite set at the end phase of the searching process. The proposed algorithm is compared with some existing approaches from the literature on classical benchmark instances. Computational results show that the proposed algorithm outperforms the existing ones and is suitable for optimizing the manufacturing process in steelworks.

This paper considers the workflow scheduling problem in Clouds with the hourly charging model and data transfer times. It deals with the allocation of tasks to suitable VM instances while maintaining the precedence constraints on one hand and meeting the workflow deadline on the other. A bi-direction adjust heuristic (BDA) is proposed for the considered problem. Matching of tasks and the VM types is modeled as Mixed Integer Linear programming (MILP) problem and solved using CPLEX at the first stage of BDA. In the second stage, forward and backward scheduling procedures are applied to allocate tasks to VM instances according to the result of the first stage. In the backward scheduling procedure, a priority rule considering the finish time, wasted time fractions and added hours is developed to make appropriate matches of tasks and free time slots. Extensive experimental results show that the proposed BDA heuristic outperforms the existing state-of-the-art heuristic ICPCP in all cases. Further, compared with ICPCP, about 80% percentage of VM renting cost is saved for instances with 900 tasks at most.

In this paper, IILS (Integrated Iterated Local Search) is proposed for the permutation flow shop scheduling problem with the total tardiness minimization. Local searches are performed on an initial solution generated by NEHEDD. Insertion and swapping neighborhood structures are constructed, based on which an integrated neighborhood structure is investigated. In terms of the integrated neighborhood structure, the local search exploits the search space with strong intensification. To increase the diversification of IILS, a composite perturbation procedure is introduced, which performs either an insertion or swapping perturbation operation with a probability. The perturbation procedure is utilized to generate a candidate list of new start points for the next iteration of local searches. The new start point is selected according to a defined criterion, which takes into account both the distance factor and the objective function difference factor. Experimental results show that the proposed algorithm outperforms three existing best sequential meta-heuristics for the considered problem on most of the 60 benchmark instances in effectiveness with the same computation time limitation.

In this paper, the bi-criteria no-idle permutation flow shop scheduling problem (NIPFS) with make span and mean tardiness minimization is considered. A pareto-based shuffled frog leaping algorithm (PSFL) is proposed. A shuffled frog leaping algorithm(SFLA) oriented updating mechanism is developed for the discrete combinatorial optimization. An insert-neighborhood-based local search is incorporated into PSFL to speed up the finding of optimal solutions. The proposal is compared with NSGAII, adapted to the considered problem, on modified Tail lard benchmarks with the same computation time. Experimental results show that the proposal outperforms NSGAII in effectiveness on average but it is outperformed by NSGAII on large size instances. The abstract goes here.

Big data analysis is very hot in cloud computing environments. How to automatically map heterogeneous data with the same semantics is one of the key problems in big data analysis. A big data clustering method based on the MapReduce framework is proposed in this paper. Big data are decomposed into many data chunks for parallel clustering, which is implemented by Ant Colony. Data elements are moved and clustered by ants according to the presented criterion. The proposed method is compared with the MapReduce framework based k-means clustering algorithm on a great amount of practical data. Experimental results show that the proposal is much effective for big data clustering.

In this paper, Harmony Search is applied to the blocking job shop problem with makespan minimization. According to the characteristics of the considered problem, a decoding method is introduced to generate feasible solutions. A rule is proposed to improvise new harmonies. Some approaches are developed to determine the harmony search considering rate, the pitch adjusting rate, the dynamic harmony memory. A local search is investigated to further improve quality of the solutions. Results of numerical experiments on classical benchmark instances show that the proposed algorithm can improve makespan 16.50% on average.

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.

In this paper, an efficient iterated greedy algorithm is proposed for the SDST (Sequence Dependent Setup Time) no-wait flowshop with makespan minimization, which is known to be NP-hard. By introducing effective operators, the Iterated Greedy algorithm is adapted to the considered problem. To improve the quality of solutions, Local Search is incorporated into the modified Iterated Greedy algorithm. The proposed algorithm is compared with BIH, GAPH1-GAPH4, and IG_Ruiz on Taillard's instances of ssd10, ssd50, ssd100, and ssdl25. Experimental results demonstrate that the proposal outperforms BIH and GAPH1-GAPH4. As well, the proposal is more effective than IG_Ruiz under the same computation-time criterion.

In this paper, the service scheduling problem with start time constraints is considered for distributed collaborative manufacturing systems, which is different from the discrete time-cost tradeoff problem (DTCTP), well studied during the past decades. The assumption that the ability of services is unlimited in DTCTP is seldom true for practical settings. The fact that most services have limited capabilities, especially for manufacturing services results in constraint start times for requirements. Such a DTCTP is modeled as the DTCTP-STC (discrete time-cost tradeoff problem with start time constraints), also proved to be NP-hard. A service is just available at some time point, which can be assigned as the start time negotiated between a broker and a provider. An effective dynamic programming algorithm is proposed with the time complexity O(N2Mv+1) for the DTCTP-STC. The impact of the number of nodes, the number of modes, and the complexity of the network on the computation time is analyzed by experiments. Simulated experiments are performs on randomly generated instances. The results illustrated that the proposal is very effective for small size instances. As well, the proposal is more suitable for the DTCTP-STC than the DTCTP with faster convergent speed for those general instances with fixed fewer modes.

In this paper, a multi-mode project scheduling problem with deadline constraints is considered to minimize the resource availability cost. Modes of each activity are associated with different durations and renewable resources. Three kinds of rules are developed for activity selection, mode assignment, and time decision, respectively. A lot of combinations of the three kind rules are compared and the choosing probabilities are determined, based on which a regret probability based stochastic (RPBS) method is proposed for the considered problem. Computational results demonstrate that the RPBS method outperforms the existing one and the rule combinations in effectiveness but with a little more computation time.

Distributed, collaborative, and integrated product development with dynamic and reconfigurable manufacturing environments require more holistic information model to support its use throughout the product lifecycle. In this paper, a multiple dimensional in-process workpiece (MDIPW) is created based on dynamic feature information model (DFIM). The MDIPW is able to adjust its forms of expression through creating associations between feature-based models and manufacturing resources. These associations as representation of knowledge are embedded into the MDIPW, and make it more intelligent. The generated inprocess workpiece is a solid model which can be used for other purposes, such as inspection points generation.

In this paper, adaptive hybrid genetic algorithms (AHA0~ AHA3) are proposed for the sequence-dependent setup times permutation flow shop scheduling problem with the objectives to minimize makespan and total weighted tardiness, both of which will be considered separately. Each job is assigned an introduced inheriting factor, which indicates the probability that the job is copied to the same position of the offspring individual during crossover and is dynamically updated. Good genes and bad genes can be mined by inheriting factors. Probability-based Multi-Point Crossover (PMPC) is constructed to inherit good genes with high probabilities to the offspring and destroy bad genes with high probabilities. Inheriting factors determine such probabilities and the genetic algorithm evolves adaptively and is denoted as AHA0. Three local search methods (LS1, LS2, and LS3) are separately integrated with AHA0and three hybrid algorithms AHA1~ AHA3are developed. Compared with GA_RMA and CPSO (effective algorithms without integrating any local search), AHA0is the most effective. Another six hybrid algorithms are extended from IG_RS (the current best algorithm for the two considered problems) and CPSO by integrating with the three local search methods and they are compared with AHA1~ AHA3comprehensively. Experimental results show that for the two considered problems, AHA1outperforms the other algorithms on small setup-time instances and AHA3is the most effective algorithm among the compared ones on big setup-time instances, while the computation time of AHA1is moderate among the LS1 integrated algorithms, so is AHA3. The effects of the key factors or parameters on algorithms are analyzed as well.

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 this paper, no-wait flow shop scheduling problem with flowtime minimization is considered. Objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An evolutionary algorithm (EA) is proposed for the considered problem. The initial population with two members is generated by different heuristics. After crossover, the disturb cycles which consist of a mutation operator and strengthen approaches are conducted to the offspring. EA is compared with the best-so-far algorithms SRTS, PH1p and DPSOvndon 110 benchmark instances. Experimental results show that EA outperforms the others on effectiveness but is a little worse than DPSOvndon 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, a RFID-based method is proposed for resource localization and dual-command generation in unit-load warehouse environments. A novel framework is constructed by deploying two types of passive tags respectively on grounds and racks as reference points (serve as landmarks) in warehouses. The number of readers can be decreased greatly without losing localization accuracy. Readers are installed on handling equipment (forklifts) to identify reference tags for resource localization when performing operations. The class-based strategy for storage assignment and dual-command generating mechanism are adopted. The travelling distance in warehouse can be reduced obviously by dual-command operations, which is analyzed using the expected travelling distance model. As well, experimental results show that readers can identify tags accurately in a reasonable distance to meet practical requirements.

Resources should be virtualized before they are deployed to cloud manufacturing systems. In this paper, a method is proposed for resource virtualization by transforming manufacturing resources into cloud services through two phases. Manufacturing resource features are comprehensively analyzed. A virtual specification is established for describing heterogeneous manufacturing resources in an isomorphic manner. By extracting characteristics of resources, an algorithm is proposed for resources partitioning according to manufacturing capabilities. Resources are encapsulated as cloud services and deployed to the cloud service platform, where manufacturing resources can be shared and accessed by heterogeneous applications in cloud manufacturing systems.

In this paper, hatch constrained quay crane scheduling problem is considered to minimize makespan with dual cycling, which can improve efficiency of operations and utilization of quay cranes. By analyzing precedence relationships intra- and inter- hatches, the problem is decomposed into two embedded sub-problems, each of which can be formulated as a 2-machine flow shop scheduling problem. A composite heuristic is introduced for stacks scheduling in a hatch by integrating the Johnson rule with a developed gap-shifting strategy. A better model is constructed for inter-hatches than existing ones, in which overlapped processing time is shorten and effectiveness can be improved by a reconstructive Johnson rule. Experimental results show that the proposed composite algorithm outperforms the existing hybrid heuristic.

In this paper, operators are encapsulated by services in algorithms for large-scale optimization problems and the services are deployed in distributed systems. Response time is an important factor for the performance of cooperative services. The message parse time is analyzed. Initial service accessing time is the main overhead for service calling. To decrease both the initial time and the response time, SBP (Service Buffering Pool based Scheduling Algorithm) is proposed by integrating a resource pool with a cache. Appropriate number of computing resources can be determined for large-scale optimization problems after analyzing the influence of the number of computing resources on algorithms. The proposed algorithm is compared with a centralized algorithm and a distributed algorithm without cache. Experimental results show that the proposed algorithm has a lower overhead than the other two algorithms.

In Spiking neural networks, information is encoded in separate spike times. The traditional gradient descent based learning algorithm (SpikeProp) trends to be trapped in local optima and cannot converge if the negative synaptic weights are allowed. In this paper, a cooperative PSO (Particle Swarm Optimization) method is proposed for its supervised learning. A simplified neural network structure is suggested. The CPSO-based learning method can improve both the weights of the spike neurons and the delays between the neurons. Both the positive and negative weights can be preserved by the biological neurons. Experiments on benchmark problems show the proposal is reliable and efficient for learning spike patterns.

As one of the key characteristics of software as a Service (SaaS), multi-tenancy aims to support massive customers by sharing application instances and databases. To achieve the high economies of scale, one of the most issues needing to be solved in the real industry is that, given a fixed number of nodes, how to optimally place on-boarding tenants to maximize the total supported number of tenants without violating their SLA requirements. This paper focuses on this problem, which is called On-line Tenant Placement Problem (OTPP). In order to calculate the resource consumption of on-boarding tenants, a novel resource consumption estimation model for multi-tenant pattern is proposed in this paper. Based on this model, we explore the complexity of OTPP. A robust heuristic is proposed for the OTPP. The simulation experimental results show the high effectiveness and the good efficiency of our algorithm.

In this paper, a Quantum-inspired Iterated Greedy algorithm (QIG) is proposed for permutation flowshops with the objective to minimize the total flowtime. A hybrid representation is adopted to construct a Q-job by combining a job with a Q-bit. Solutions denoted by permutations of Q-jobs can be evaluated directly. The initial solution is generated by an effective heuristic, in which the Q-bits of the Q-jobs are experimentally determined. A new rotation gate is proposed to update Q-bits based on Particle Swarm Optimization (PSO). Different from traditional Iterated Greedy algorithms, the proposed rotation gate can dynamically adapt the perturbation strength by taking into account both the current solution and the best one. Experimental results show that QIG outperforms other existing algorithms for the considered problem.

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, NP-hard no-wait flowshop scheduling problems with makespan minimization are considered. An iterative local search method is proposed which performs a randomized walk in the space of local optima until some stop criterion is satisfied. A perturbation mechanism and a compound neighborhood operator (or move ) are presented. The proposal is compared with the best algorithm so far. Experimental results show the proposed algorithm outperforms the existing one in effectiveness and in efficiency.

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.

Cost optimization for workflow applications with deadline constraints is fundamental and intractable in grids. In this paper, early tree is introduced to find an early feasible schedule for a workflow application. According to the early tree, a cost optimization algorithm is proposed. Taking into account the workflow total float, the workflow deadline is segmented to activity deadlines while keeping precedence constraints. Costs of all activities are locally optimized, so does the workflow cost. Experimental results show that the proposal that this approach can dramatically decrease workflow cost with different deadlines. Moreover, it outperforms other two leveling algorithms in performance on average.

In this paper, a Web Service based method is presented to conduct parallelized operations in an algorithm on multiple computers. Parallelizable operations in a constructive heuristic for flow shop scheduling problem with total flowtime minimization are analyzed. A parallel heuristic for the problem is described and its parameters are analyzed in theory. The proposed parallel heuristic is compared with the corresponding centralized one. Experimental results show that the proposed method can substantially increase efficiency.

In this paper, no-wait flow shop scheduling problem with total flowtime minimization is considered. A hybrid heuristic is proposed, which is based on PHI (p) (presented by Aldowaisan and Allahverdi, OMEGA, 2004). A composite algorithm is adopted to generate the initial seed. Job insertion in PHI (p) is replaced with an existing constructive heuristic. Experimental results show that the proposal outperforms PHI (p), especially for large scale instances.

In this paper, permutation flow shop scheduling problem with total flowtime minimization is considered. Two composite heuristics, CH1 and CH2, are proposed which use LR (developed by Liu & Reeves) as index development phase and iterative RZ+FPE-R procedure as solution improvement phase. CH2 also adopts FL to construct a solution. CH1 and CH2 are compared with FLR1, FLR2 and IH7_FL (the best existing composite heuristics for the problem considered in this paper) both in effectiveness and in efficiency. Computational results show that CH1 is the best among the five heuristics in effectiveness and CH2 outperforms the other three. Though time complexity of the five is identical, CPU-time needed by CH1 is at the medium and CH2 is the most time-consuming

In this paper, an objective increment method is introduced for no-wait flow shops with makespan minimization, which can calculate makespan of a new schedule directly from that of its parent and can judge whether the new schedule is better than its parent or not. Specific makespan increments are analyzed for insertion and pair-wise exchange, two fundamental operations in most heuristics for flow shops. Moreover, a composite heuristic based on makespan increment is proposed. Experimental results show that the proposal outperforms the best existing algorithms SA2, RAJ and GR for the problem considered and it needs minimal CPU time among the four compared algorithms, which implies that the proposal is desirable for large-scale no-wait flow shops in practical manufacturing systems

Service resources allocation and scheduling is one of the challenging and complex problems in computation-economy-driven open grid service architecture. This paper proposes a time-cost tradeoff workflow scheduling algorithm in which cost is optimized for schedules with the expectation to minimize workflow duration. Dynamic service selection strategy is adopted to adapt to dynamic shared and autonomous resources in grids. Simulation results show that the algorithm can achieve less completion time and lower cost which can meet requirements in practical applications