Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 7
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Group Scheduling With Nonperiodical Maintenance and Deteriorating Effects

  • Xu, Haiyan
  • Li, Xiaoping
  • Ruiz García, Rubén
  • Zhu, Haihong
[EN] 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, This work was supported in part by the National Key Research and Development Program of China under Grant 2017YFB1400801, in part by the National Natural Science Foundation of China under Grant 61572127, Grant 61872077, and Grant 61832004, and in part by the Collaborative Innovation Center of Wireless Communications Technology. The work of R. Ruiz was supported by the Spanish Ministry of Economy and Competitiveness through the Project "SCHEYARD-Optimization of Scheduling Problems in Container Yards" with FEDER funds under Grant DPI2015-65895-R. This paper was recommended by Associate Editor W. Shen
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Multi-Queue Request Scheduling for Profit Maximization in IaaS Clouds

  • Wang, Shuang
  • Li, Xiaoping
  • Sheng, Quan Z.
  • Ruiz García, Rubén
  • Zhang, Jinquan
  • Beheshti, Amin
[EN] 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., This work was supported in part by the National Key Research and Development Program of China under Grant 2017YFB1400800, in part by the National Natural Science Foundation of China under Grants 61872077 and 61832004, and in part by the Collaborative InnovationCenter of Wireless Communications Technology. The work of Quan Z. Sheng was supported in part by Australian Research Council Future Fellowship under Grant FT140101247 and in part by Discovery Project under Grant DP180102378. The work of Ruben Ruiz was supported in part by the Spanish Ministry of Science, Innovation, and Universities through the project OPTEP-Port Terminal Operations Optimization under Grant RTI2018-094940-B-I00 financed with FEDER funds
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Hybrid resource provisioning for cloud workflows with malleable and rigid tasks

  • Chen, Long
  • Li, Xiaoping
  • Guo, Yucheng
  • Ruiz García, Rubén
[EN] 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., l This work is supported by the National Key Research and Development Program of China (No. 2017YFB1400801), the National Natural Science Foundation of China (Nos. 61572127, 61872077, 61832004) and Collaborative Innovation Center of Wireless Communications Technology. Rub~en Ruiz is supported by the Spanish Ministry of Economy and Competitiveness, under the project "SCHEYARD-Optimization of scheduling problems in container yards" (No. DPI2015-65895-R) partly financed with FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Allocating MapReduce workflows with deadlines to heterogeneous servers in a cloud data center

  • Wang, Jia
  • Li, Xiaoping
  • Ruiz García, Rubén
  • Xu, Hanchuan
  • Chu, Dianhui
[EN] Total profit is one of the most important factors to be considered from the perspective of resource providers. In this paper, an original MapReduce workflow scheduling with deadline and data locality is proposed to maximize total profit of resource providers. A new workflow conversion based on dynamic programming and ChainMap/ChainReduce is designed to decrease transmission times among MapReduce jobs of workflows. A new deadline division considering execution time, float time and job level is proposed to obtain better deadlines of MapReduce jobs in workflows. With the adapted replica strategy in MapReduce workflow, a new task scheduling is proposed to improve data locality which assigns tasks to servers with the earliest completion time in order to ensure resource providers obtain more profit. Experimental results show that the proposed heuristic results in larger total profit than other adopted algorithms., This work is supported by the National Key Research and Development Program of China (No. 2017YFB1400801), the National Natural Science Foundation of China (Nos. 61872077, 61832004) and Collaborative Innovation Center of Wireless Communications Technology. Rubén Ruiz is partly supported by the Spanish Ministry of Science, Innovation, and Universities, under the project ¿OPTEP-Port Terminal Operations Optimization¿ (No. RTI2018-094940-B-I00) financed with FEDER funds¿.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Scheduling Workflows With Limited Budget to Cloud Server and Serverless Resources

  • Jinquan Zhang
  • Li, Xiaoping
  • Long Chen
  • Ruiz García, Rubén
[EN] 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., This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFB3305500, in part by the National Natural Science Foundation of China under Grants 62273089, 62102080, and 61832004, in part by Natural Science Foundation of Jiangsu Province under Grant BK20210204, in part by the Fundamental Research Funds for the Central Universities under Grant 2242022R10017, and in part by Collaborative Innovation Center of Wireless Communications Technology.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Scheduling Periodical Multi-Stage Jobs With Fuzziness to Elastic Cloud Resources

  • Zhu, Jie
  • Li, Xiaoping
  • Ruiz García, Rubén
  • Li, Wei
  • Huang, Haiping
  • Zomaya, Albert Y.
[EN] 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., This work was supported by the National Key Research and Development Program of China (No. 2017YFB1400800), the National Natural Science Foundation of China (Nos. 61672297, 61872077, and 61832004), the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 18KJB520039) and the National Science Foundation for Post-doctoral Scientists of China (Grant No. 2018M640510). Ruben Ruiz was partially supported by the Spanish Ministry of Science, Innovation, and Universities, under the project "OPTEP-Port Terminal Operations Optimization" (No. RTI2018-094940-B-I00) financed with FEDER funds. The authors would like to thank the anonymous reviewers for their valuable feedback on this work.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Performance Analysis for Heterogeneous Cloud Servers Using Queueing Theory

  • Wang, Shuang
  • Li, Xiaoping
  • Ruiz García, Rubén
[EN] 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., This work is supported by the National Key Research and Development Program of China Grant No. 2017YFB1400801, the National Natural Science Foundation of China Grant Nos. 61572127, 61872077, 61832004 and Collaborative Innovation Center of Wireless Communications Technology. Rub~en Ruiz is partly supported by the Spanish Ministry of Science, Innovation, and Universities, under the project "OPTEP-Port Terminal Operations Optimization" (No. RTI2018-094940-BI00) financed with FEDER funds.