Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-16T11:42:54Z
No. of bitstreams: 1
arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5) / Made available in DSpace on 2017-08-16T11:42:54Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5)
Previous issue date: 2016-07-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The problem of scheduling on a single machine, proven to be NP-hard, consists of
de ning the job grouping in batches and of the sequence in which these batches will be
processed on a machine. Each job is associated with a release date, a processing time, a
due date, a priority level in relation to the others and a size. The machine is able to process
a group of jobs (batch) simultaneously, provided that the sum of the job sizes belonging to
the referred batch does not exceed the machine capacity. Each job must be processed only
once and only one batch is processed at a time on the machine. In this work, we consider
the objective as the minimization of total weighted tardiness, where the tardiness of a job
is the di erence between its completion time and its due date, in case the job processing
is nished after its due date and hence is late, or equals zero, otherwise. In the literature,
this problem is usually referred to as 1jbatch; rj ; sj ; comptjPwjTj . When all jobs are
available to be processed at time zero, the problem is usually represented as 1jbatch; sj ;
comptjPwjTj . These problems are still poorly explored in the literature and in addition,
cover a large number of variant forms. There are few studies involving the application of
exact methods for solving both. Only one mathematical formulation was identi ed in the
literature for these problems. Hence, four time-indexed formulations were developed to
solve the aforementioned problems, one of which is capable of dealing with both problems.
The results achieved by the developed models were compared between themselves and with
the results of the model available in the literature. These computational results reveal that
two of the proposed models obtained higher performance both in terms of quality of the
solution, particularly regarding the achieved lower bounds, and in numbers of open nodes
and of proven optimal solutions. / O problema de sequenciamento de lotes da produ c~ao em uma m aquina, comprovadamente
tido como NP-dif cil, consiste na de ni c~ao do agrupamento de tarefas em lotes
e da sequ^encia em que estes ser~ao processados em uma m aquina. Cada tarefa est a associada
a uma data de libera c~ao, um tempo de processamento, uma data de entrega, um
n vel de prioridade em rela c~ao as demais, e um tamanho. A m aquina e capaz de processar
um conjunto de tarefas (lote) simultaneamente, contanto que a soma dos tamanhos das
tarefas pertencentes ao referido lote respeite a capacidade da m aquina. Cada tarefa deve
ser processada apenas uma vez e somente um lote e processado por vez na m aquina. Neste
trabalho, considera-se como objetivo a minimiza c~ao do total de atrasos ponderados, onde
o atraso de uma tarefa e igual ao seu tempo de t ermino menos a sua data de entrega,
caso o processamento da tarefa seja nalizado ap os a sua data da entrega e, portanto, em
atraso, e e igual a zero, caso contr ario. Na literatura, este problema e geralmente referenciado
como 1jbatch; rj ; sj ; comptjPwjTj . Quando todas as tarefas est~ao dispon veis para
serem processadas no instante de tempo zero, o problema e usualmente representado por
1jbatch; sj ; comptjPwjTj . Estes s~ao problemas ainda pouco investigados na literatura
e, al em disso, abordam uma grande quantidade de variantes. Existem poucos trabalhos
envolvendo a aplica c~ao de m etodos exatos para a resolu c~ao de ambos. Apenas uma formula
c~ao matem atica foi identi cada na literatura para estes problemas. Dessa forma,
quatro formula c~oes matem aticas com vari aveis indexadas no tempo foram desenvolvidas
para resolver os problemas mencionados anteriormente, das quais uma e capaz de tratar de
ambos os problemas. Os resultados alcan cados por meio dos modelos desenvolvidos foram
comparados entre si e com os resultados do modelo dispon vel na literatura. Tais resultados
computacionais demonstram que dois dos modelos propostos obtiveram desempenho
superior tanto em termos de qualidade da solu c~ao, em especial em rela c~ao aos limites inferiores
alcan cados, quanto em n umeros de n os abertos e quantidade de solu c~oes otimas
comprovadas.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/9265 |
| Date | 04 July 2016 |
| Creators | Araújo, Katyanne Farias de |
| Contributors | Subramanian , Anand |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Informática, UFPB, Brasil, Informática |
| 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:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 4679641312648529202, 600, 600, 600, 600, 7879657947546587587, 3671711205811204509, 2075167498588264571 |
Page generated in 0.002 seconds