Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Problems of scheduling on batch processing machines to minimize makespan are widely
exploited by academic literature, mainly motivated by reliability testing in the semiconductor
industry. These problems consist in grouping jobs as a batch and scheduling the processing in
single or parallel machines. The jobs have non-identical processing times and non-identical
sizes and the total size of the batch cannot exceed the machine capacity. The processing time
of a batch is given by the longest processing time of any job in the batch. Jobs with nonidentical
release times can also be considered, and in this case a batch can only be processed
after the job with the longest release time in the batch is available. We consider four different
problems of scheduling on batch processing machines with non-identical job size and
different characteristics: single batch processing machine (1|sj,B|Cmax), single batch
processing machine with non-identical job release times (1|rj,sj,B|Cmax), identical parallel
batch processing machines (Pm|sj,B|Cmax), and identical parallel batch processing machines
with non-identical job release times (Pm|rj,sj,B|Cmax). New mathematical models are proposed
with formulations that exploit characteristics of each problem. The mathematical models are
solved using CPLEX and the computational results show that the proposed models performed
better than other models from literature. The new models for 1|sj,B|Cmax and 1|rj,sj,B|Cmax are
compared with previously published meta-heuristics and the results show that the models
provide better solutions than meta-heuristics methods with competitive computational times. / Problemas de minimização do makespan no dimensionamento e programação de bateladas
em máquinas de processamento são extensamente explorados pela literatura acadêmica,
motivados principalmente por testes de confiabilidade na indústria de semicondutores. Estes
problemas consistem em agrupar tarefas em bateladas e programar o processamento em uma
ou mais máquinas em paralelo. As tarefas possuem tempos de processamento e tamanhos não
idênticos e o tamanho total da batelada não pode exceder a capacidade da máquina. Para cada
batelada é definido um tempo de processamento que será igual ao maior tempo de
processamento das tarefas que foram alocadas a ela. As tarefas podem considerar também
tarefas com tempos de liberação não idênticos, neste caso as bateladas só poderão ser
processadas depois que a tarefa com o maior tempo de liberação for disponibilizada. Este
trabalho aborda quatro diferentes problemas de dimensionamento e programação de bateladas
com tarefas de tamanhos não idênticos, que consideram diferentes características: máquina de
processamento única (1|sj,B|Cmax), máquina de processamento única e tarefas com tempos de
liberação não idênticos (1|rj,sj,B|Cmax), máquinas de processamento paralelas idênticas
(Pm|sj,B|Cmax) e máquinas de processamento paralelas idênticas e tarefas com tempos de
liberação não idênticos (Pm|rj,sj,B|Cmax). São propostos novos modelos matemáticos com
formulações que exploram características de cada problema. Os modelos matemáticos são
resolvidos utilizando CPLEX e os resultados computacionais comprovam que os modelos
propostos possuem um desempenho melhor do que outros modelos da literatura. Os modelos
propostos para 1|sj,B|Cmax e 1|rj,sj,B|Cmax são comparados com meta-heurísticas previamente
publicadas e os resultados mostram que os novos modelos oferecem soluções melhores com
tempos computacionais competitivos.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsm.br:1/5432 |
| Date | 19 March 2014 |
| Creators | Trindade, Renan Spencer |
| Contributors | Müller, Felipe Martins, Köhler, Viviane Cátia, Fampa, Marcia Helena Costa |
| Publisher | Universidade Federal de Santa Maria, Programa de Pós-Graduação em Informática, UFSM, BR, Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFSM, instname:Universidade Federal de Santa Maria, instacron:UFSM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 100300000007, 400, 500, 300, 500, 300, 71f97871-5101-4fa8-b821-aa730e3775c4, 0df43bc1-6342-45c2-a3c0-98472ac2d453, 4ec91eb7-5288-4886-95ce-858a31b8b382, 8bf5728b-3b33-4a03-a254-0bf0f6edebc6 |
Page generated in 0.0022 seconds