Pasar al contenido principal

Resultados relacionados

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

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

Cloud Workflow Scheduling with Deadlines and Time Slot Availability

  • Li, Xiaoping
  • Qian, L.
  • Ruiz García, Rubén
[EN] 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., This work has been supported by the National Natural Science Foundation of China (Nos. 61572127, 61272377) and the Key Research & Development Program in Jiangsu Province (No. BE2015728). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "RESULT - Realistic Extended Scheduling Using Light Techniques" (No. DPI2012-36243-C02-01) partially financed with FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects

  • Li, Xiaoping
  • Yang, Z.
  • Ruiz García, Rubén
  • Chen, T.
  • Sui, S.
[EN] This paper addresses a sequence dependent setup times no-wait flowshop with learning and forgetting effects to minimize total flowtime. This problem is NP-hard and has never been considered before. A position-based learning and forgetting effects model is constructed. Processing times of operations change with the positions of corresponding jobs in a schedule. Objective increment properties are deduced and based on them three accelerated neighbourhood construction heuristics are presented. Because of the simplicity and excellent performance shown in flowshop scheduling problems, an iterated greedy heuristic is proposed. The proposed iterated greedy algorithm is compared with some existing algorithms for related problems on benchmark instances. Comprehensive computational and statistical tests show that the presented method obtains the best performance among the compared methods. (C) 2018 Elsevier Inc. All rights reserved., This work is supported by the National Natural Science Foundation of China (Nos. 61572127, 61272377), the Collaborative Innovation Center of Wireless Communications Technology and the Key Natural Science Fund for Colleges and Universities in Jiangsu Province (No. 12KJA630001). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness(MINECO), under the project "SCHEYARD - Optimization of Scheduling Problems in Container Yards" with reference DPI2015-65895-R.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Heuristics for periodical batch job scheduling in a MapReduce computing framework

  • Xiaoping Li
  • Tianze Jiang
  • Ruiz García, Rubén
Task scheduling has a significant impact on the performance of the MapReduce computing framework. In this paper, a scheduling problem of periodical batch jobs with makespan minimization is considered. The problem is modeled as a general two-stage hybrid flow shop scheduling problem with schedule-dependent setup times. The new model incorporates the data locality of tasks and is formulated as an integer program. Three heuristics are developed to solve the problem and an improvement policy based on data locality is presented to enhance the methods. A lower bound of the makespan is derived. 150 instances are randomly generated from data distributions drawn from a real cluster. The parameters involved in the methods are set according to different cluster setups. The proposed heuristics are compared over different numbers of jobs and cluster setups. Computational results show that the performance of the methods is highly dependent on both the number of jobs and the cluster setups. The proposed improvement policy is effective and the impact of the input data distribution on the policy is analyzed and tested., This work is supported by the National Natural Science Foundation of China (No. 61272377) and the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20120092110027). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "RESULT - Realistic Extended Scheduling Using Light Techniques" (No. DPI2012-36243-C02-01) partially financed with FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Resource Renting for Periodical Cloud Workflow Applications

  • Chen, Long
  • Li, Xiaoping
  • Ruiz García, Rubén
[EN] 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., This work is supported by the National Natural Science Foundation of China (No. 61572127, 61272377), the Key Research & Development program in Jiangsu Province (No. BE2015728) and Collaborative Innovation Center of Wireless Communications Technology. Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "SCHEYARD-Optimization of Scheduling Problems in Container Yards" (No. DPI2015-65895-R) financed by FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects

  • Wang, Yamin
  • Li, Xiaoping
  • Ruiz García, Rubén
[EN] 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., This work was supported in part by the National Natural Science Foundation of China under Grant 61572127 and Grant 61272377, and in part by the Specialized Research Fund for the Doctoral Program of Higher Education under Grant 20120092110027. The work of R. Ruiz was supported in part by the Spanish Ministry of Economy and Competitiveness under Project "RESULT-Realistic Extended Scheduling Using Light Techniques" under Grant DPI2012-36243-C02-01, and in part by the FEDER.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Methods for Scheduling Problems Considering Experience, Learning, and Forgetting Effects

  • Li, Xiaoping
  • Jiang, Y.
  • Ruiz García, Rubén
[EN] 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., This work was supported in part by the National Natural Science Foundation of China under Grant 61572127 and Grant 61272377, in part by the Key Research and Development Program in Jiangsu Province under Grant BE2015728, in part by the Collaborative Innovation Center of Wireless Communications Technology and the Key Natural Science Fund for Colleges and Universities in Jiangsu Province under Grant 12KJA630001, 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 Project "SCHEYARD-Optimization of Scheduling Problems in Container Yards" under Grant DPI2015-65895-R. This paper was recommended by Associate Editor A. Janiak.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Idle block based methods for cloud workflow scheduling with preemptive and non-preemptive tasks

  • Chen, Long
  • Li, Xiaoping
  • Ruiz García, Rubén
[EN] Complex workflow applications are widely used in scientific computing and economic analysis, which commonly include both preemptive and non-preemptive tasks. Cloud computing provides a convenient way for users to access different resources based on the ¿pay-as-you-go¿ model. However, different resource renting alternatives (reserved, on-demand or spot) are usually provided by the service provider. The spot instances provide a dynamic and cheaper alternative comparing to the on-demand one. However, failures often occur due to the fluctuations of the price of the instance. It is a big challenge to determine the appropriate amount of spot and on-demand resources for workflow applications with both preemptive and non-preemptive tasks. 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 for the considered problem. Different idle time block-based searing and improving strategies are developed 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., This work is supported by the National Natural Science Foundation of China (No. 61572127, 61272377), the National Key Research and Development Program of China (No. 2017YFB1400800). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "SCHEYARD - Optimization of Scheduling Problems in Container Yards" (No. DPI2015-65895-R) financed by FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An effective heuristic for project scheduling with resource availability cost

  • Zhu, Xia
  • Ruiz García, Rubén
  • Li, Shiyu
  • Li, Xiaoping
[EN] The resource constrained project scheduling problem (RCPSP) is widely studied in the literature and has a host of applications in practice. As a variant of the RCPSP, the resource availability cost problem (RACP), which has the aim of minimizing the availability costs of renewable resources in order to complete a project subject to a given deadline, is considered in this paper. We divide the RACP into two sub-problems: the sequencing problem and the resource decision problem, and propose a multi-start iterative search heuristic (MSIS) to solve it. For the sequencing problem, an iterative search framework is constructed to effectively search the activity sequences. A two stage resource adjustment procedure and a backward peak elimination procedure is developed for solving the resource decision problem. MSIS is compared with three existing algorithms on both PSPLib and RanGen data sets involving 1380 instances. A complete calibration of the different parameters and operators of MSIS by means of a design of experiments approach is given. Experimental and statistical results show that MSIS outperforms the other three algorithms in both effectiveness and efficiency by a significant margin. (C) 2016 Published by Elsevier B.V., This work is supported by the National Natural Science Foundation of China (Nos. 61572127, 61272377), the Key Research & Development program in Jiangsu Province (No. BE2015728) and the Collaborative Innovation Center of Wireless Communications Technology. Rubén Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project SCHEYARD - Optimization of Scheduling Problems in Container Yards with reference DPI2015-65895-R co-financed with FEDER funds.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An Iterated Greedy Heuristic for Mixed No-Wait Flowshop Problems

  • Wang, Yamin
  • Li, Xiaoping
  • Ruiz García, Rubén
  • Sui, S.
[EN] 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., This work was supported in part by the National Natural Science Foundation of China under Grant 61572127 and 61272377, in part by the Key Research and Development Program in Jiangsu Province under Grant BE2015728, and in part by the Collaborative Innovation Center of Wireless Communications Technology. The work of R. Ruiz was supported in part by the Spanish Ministry of Economy and Competitiveness through the project "SCHEYARD-Optimization of Scheduling Problems in Container Yards" under Grant DPI2015-65895-R, and in part by the FEDER Funds.