Artigos

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

Navegar

Filtros

2017 - 20193

Configurações

Data inicial: 2010Data final: 2019Assunto: search.filters.subject.Scheduling

Resultados da Pesquisa

Agora exibindo 1 - 3 de 3
  • Imagem de Miniatura
    Item
    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
  • Imagem de Miniatura
    Item
    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.
  • Imagem de Miniatura
    Item
    Iterated greedy with random variable neighborhood descent for scheduling jobs on parallel machines with deterioration effect
    (Electronic Notes in Discrete Mathematics, 2017-04-14) Santos, Vívian L. Aguiar; Arroyo, José Elias C.
    In this paper, we study an unrelated parallel machine scheduling problem in which the jobs cause deterioration of the machines. This deterioration decreases the performance of the machines, and therefore, the processing times of the jobs are increased over time. The problem is to find the processing sequence of jobs on each machine in order to reduce the deterioration of the machines and consequently minimize the makespan. This problem is NP-hard when the number of machines is greater or equal than two, and hence we propose a heuristic based on the Iterated Greedy meta-heuristic coupled with a variant of the Variable Neighborhood Descent method that uses a random ordering of neighborhoods in local search phase. The performance of our heuristic, named IG-RVND, is compared with the state-of-the-art meta-heuristic proposed in the literature for the problem under study. The results show that the our heuristic outperform the existing algorithm by a significant margin.