The literature reviewed on lot-sizing models with random yields is limited to certain random occurrences such as day to day administrative errors, minor machine repairs and random supply due to faulty delivery of parts. In reality however, the manufacturing industry faces other risks that are non random in nature. One example would be yield discrepancies caused by non random triggers such as a change in the production process, product or material. Yield uncertainties of these types are temporary in nature and usually pertain until the system stabilizes. One way of reducing the implications of such events is to have additional batches processed earlier in the production that can absorb the risk associated with the event. In this thesis, this particular approach is referred to as the <i>anticipatory batch insertion</i> to mitigate perceived risk. This thesis presents an exploratory study to analyze the performance of batch insertion under various scenarios. The scenarios are determined by sensitivity of products, schedule characteristics and magnitude of risks associated with causal triggers such as a process change. The results indicate that the highest return from batch insertion can be expected when there are slightly loose production schedules, high volumes of sensitive products are produced, there are high costs associated with the risks, and the risks can be predicted with some degree of certainty.

The literature reviewed on lot-sizing models with random yields is limited to certain random occurrences such as day to day administrative errors, minor machine repairs and random supply due to faulty delivery of parts. In reality however, the manufacturing industry faces other risks that are non random in nature. One example would be yield discrepancies caused by non random triggers such as a change in the production process, product or material. Yield uncertainties of these types are temporary in nature and usually pertain until the system stabilizes. One way of reducing the implications of such events is to have additional batches processed earlier in the production that can absorb the risk associated with the event. In this thesis, this particular approach is referred to as the <i>anticipatory batch insertion</i> to mitigate perceived risk. This thesis presents an exploratory study to analyze the performance of batch insertion under various scenarios. The scenarios are determined by sensitivity of products, schedule characteristics and magnitude of risks associated with causal triggers such as a process change. The results indicate that the highest return from batch insertion can be expected when there are slightly loose production schedules, high volumes of sensitive products are produced, there are high costs associated with the risks, and the risks can be predicted with some degree of certainty.

ABSTRACT A HEURISTIC APPROACH FOR THE SINGLE MACHINE SCHEDULING TARDINESS PROBLEMS &Ouml / zbakir, Saffet Ilker M.Sc., Department of Industrial Engineering Supervisor : Prof. Dr. &Ouml / mer Kirca September 2011, 102 pages In this thesis, we study the single machine scheduling problem. Our general aim is to schedule a set of jobs to the machine with a goal to minimize tardiness value. The problem is studied for two objectives: minimizing total tardiness value and minimizing total weighted tardiness value. Solving optimally this problem is difficult, because both of the total tardiness problem and total weighted tardiness problem are NP-hard problems. Therefore, we construct a heuristic procedure for this problem. Our heuristic procedure is divided to two parts: construction part and improvement part. The construction heuristic is based on grouping the jobs, solving these groups and then fixing some particular number of jobs. Moreover, we used three type improvement heuristics. These are sliding forward method, sliding backward method and pairwise interchange method. Computational results are reported for problem size = 20, 40, 50 and 100 at total tardiness problem and for problem size = 20 and 40 at total weighted tardiness problem. Experiments are designed in order to investigate the effect of three factors which are problem size, tardiness factor and relative range of due dates on computational difficulties of the problems. Computational results show that the heuristic proposed in this thesis is robust to changes at these factors.

In this paper we propose an improved algorithm to search optimal solutions to the single machine total weighted tardiness scheduling problem. We propose using longest common sequence to combine with the random key method. Numerical simulation shows that the scheme we proposed could improve the search efficiency of genetic algorithm in this problem for some cases.

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.

The purpose of this thesis is to develop a model to enhance the effectiveness of machining centers with multi-pallet automatic pallet changers (APCs). From critical literature review no existing theories within this field were found. The multi-pallet APC allows multi-setups and a more flexible sequencing of jobs. The model together with the developed heuristic scheduling algorithm with the objective to minimize the total weighted tardiness can be used to plan in n jobs on m pallets in a shop-floor. The right maintenance policy ensures a high availability, which together with the program guarantees a high level of utilization of the machinery. Consequently the effectiveness will be enhanced. A case study approach was used to test the model at Växjöfabriken in Sweden, which treats cast material. The results of this case study are a more effective utilization of the machines with decreased tardiness costs, increased customers’ satisfaction and goodwill of the company. The contribution of this thesis is a model with a flexible, adjustable and expandable heuristic scheduling algorithm, which can be applied in all manufacturing companies using machining centers with multi-pallet APCs. / Syftet med denna uppsats är att utveckla en modell för att förbättra effektiviteten av maskincentra med automatiska palletväxlare (APCs) för multi-palleter. När en kritisk litteratursökning genomfördes hittades inga relevanta teorier inom det aktuella området. Multi-pallet APC tillåter att många jobb kan förberedas samtidigt och gör planeringen av jobben mer flexibel. Modellen, tillsammans med den utvecklade heuristiska planeringsalgoritmen med målet att minimera den totala viktade förseningen, kan användas för att planera in n jobb med m palleter på ett verkstadsgolv. Rätt underhålls policy försäkrar en hög tillgänglighet vilket tillsammans med programmet garanterar en hög utnyttjandenivå av maskinerna. Som följd kommer effektiviteten att höjas. En fallstudie utfördes på Växjöfabriken i Sverige för att utvärdera modellen, på företaget efterbehandlas gjutgods. Resultatet från denna fallstudie blev ett effektivare utnyttjande av maskinerna, med minskade förseningskostnader, ökad kundtillfredställelse och goodwill för företaget. Denna uppsats bidrar med en modell och en flexibel, anpassningsbar och utvecklingsbar heuristisk planeringsalgoritm, vilken kan användas i alla industriföretag som använder maskincentra med multi-pallet APCs.

<p>The purpose of this thesis is to develop a model to enhance the effectiveness of machining centers with multi-pallet automatic pallet changers (APCs). From critical literature review no existing theories within this field were found. The multi-pallet APC allows multi-setups and a more flexible sequencing of jobs. The model together with the developed heuristic scheduling algorithm with the objective to minimize the total weighted tardiness can be used to plan in n jobs on m pallets in a shop-floor. The right maintenance policy ensures a high availability, which together with the program guarantees a high level of utilization of the machinery. Consequently the effectiveness will be enhanced. A case study approach was used to test the model at Växjöfabriken in Sweden, which treats cast material. The results of this case study are a more effective utilization of the machines with decreased tardiness costs, increased customers’ satisfaction and goodwill of the company. The contribution of this thesis is a model with a flexible, adjustable and expandable heuristic scheduling algorithm, which can be applied in all manufacturing companies using machining centers with multi-pallet APCs.</p> / <p>Syftet med denna uppsats är att utveckla en modell för att förbättra effektiviteten av maskincentra med automatiska palletväxlare (APCs) för multi-palleter. När en kritisk litteratursökning genomfördes hittades inga relevanta teorier inom det aktuella området. Multi-pallet APC tillåter att många jobb kan förberedas samtidigt och gör planeringen av jobben mer flexibel. Modellen, tillsammans med den utvecklade heuristiska planeringsalgoritmen med målet att minimera den totala viktade förseningen, kan användas för att planera in n jobb med m palleter på ett verkstadsgolv. Rätt underhålls policy försäkrar en hög tillgänglighet vilket tillsammans med programmet garanterar en hög utnyttjandenivå av maskinerna. Som följd kommer effektiviteten att höjas. En fallstudie utfördes på Växjöfabriken i Sverige för att utvärdera modellen, på företaget efterbehandlas gjutgods. Resultatet från denna fallstudie blev ett effektivare utnyttjande av maskinerna, med minskade förseningskostnader, ökad kundtillfredställelse och goodwill för företaget. Denna uppsats bidrar med en modell och en flexibel, anpassningsbar och utvecklingsbar heuristisk planeringsalgoritm, vilken kan användas i alla industriföretag som använder maskincentra med multi-pallet APCs.</p>