Artigos

URI permanente para esta coleçãohttps://locus.ufv.br/handle/123456789/11798

Navegar

Agora exibindo 1 - 4 de 4

An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times
(Engineering Applications of Artificial Intelligence, 2019-01) Arroyo, José Elias C.; Leung, Joseph Y.-T.; Tavares, Ricardo Gonçalves
This paper investigates the problem of scheduling a set of jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch machines with different capacities so as to minimize the total flow time of the jobs. The total flow time, defined as the total amount of time that the jobs spend in the system (i.e. the period between the job release dates and its completion times), is one of the most important objectives in scheduling problems, since it can lead to stable utilization of resources and reduction of working-in-process inventory. Motivated by the computational complexity of the problem, a simple and effective iterated greedy (IG) algorithm is proposed to solve it. The IG algorithm uses an efficient greedy heuristic to reconstruct solutions and a local search procedure to further enhance the solution quality. In attempting to obtain optimal solutions for small-medium size instances, a mixed integer programming model for the problem is also presented. The performance of the proposed algorithm is tested on a comprehensive set of small, medium and large benchmark of randomly generated instances, and is compared to three benchmark meta-heuristic algorithms (Discrete Differential Evolution, Ant Colony Optimization and Simulated Annealing) recently proposed for similar parallel batch machine scheduling problems. Experimental results and statistical tests show that the proposed algorithm is significantly superior in performance than the other algorithms
JetsonLEAP: A framework to measure power on a heterogeneous system-on-a-chip device
(Science of Computer Programming, 2019-03-15) Gull, Christopher; Nacif, José; Bessa, Tarsila; Quintão, Pedro; Pereira, Fernando Magno Quintão; Frank, Michael
Computer science marches towards energy-aware practices. This trend impacts not only the design of computer architectures, but also the design of programs. However, developers still lack affordable and accurate technology to measure energy consumption in computing systems. The goal of this paper is to mitigate such problem. To this end, we introduce JetsonLEAP, a framework that supports the implementation of energy-aware programs. JetsonLEAP consists of an embedded hardware, in our case, the NVIDIA Jetson TK1 development board, a circuit to control the flow of energy, of our own design, plus a library to instrument program parts. We discuss two different circuit setups. The most precise setup lets us reliably measure the energy spent by 225,000 instructions, the least precise, although more affordable setup, gives us a window of 975,000 instructions. To probe the precision of our system, we use it in tandem with a high-precision, high-cost acquisition system, and show that results do not differ in any significant way from those that we get using our simpler apparatus. Our entire infrastructure – board, power meter and both circuits – can be reproduced with about $500.00. To demonstrate the efficacy of our framework, we have used it to measure the energy consumed by programs running on ARM cores, on the GPU, and on a remote server. Furthermore, we have studied the impact of OpenACC directives on the energy efficiency of high-performance applications.
Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces
(Artificial Intelligence, 2016-01) Lelis, Levi H. S.; Stern, Roni; Arfaee, Shahab Jabbari; Zilles, Sandra; Felner, Ariel; Holte, Robert C.
Optimal planning and heuristic search systems solve state-space search problems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i.e., without actually finding a solution path of that cost. We present an algorithm, BiSS, which is a hybrid of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. BiSS is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that BiSS produces accurate predictions in several domains. In addition, we show that BiSS scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6×6, 7×7, and 8×8 Sliding-Tile puzzle and provide indirect evidence that these estimates are accurate. As a practical application of BiSS, we show how to use its predictions to reduce the time required by another system to learn strong heuristic functions from days to minutes in the domains tested.
Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times
(Computers & Operations Research, 2017-02) Arroyo, José Elías Cláudio; Leung, Joseph Y. T.
This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.