Let there be m parallel machines and n jobs to be scheduled non-preemptively. A job j scheduled on machine i takes p_{i,j} time units to complete, where 1 ≤ i ≤ m and 1 ≤ j ≤ n. For a given schedule, the makespan is the completion time of a machine that finishes last. The goal is to produce a schedule of all n jobs with minimum makespan. This is known as the makespan problem on unrelated parallel machines (UPMs), denoted as R||C_{max}. In this thesis, we focus on subclasses of R||C_{max}. Our research consists of two components. First, a survey of theoretic results for R||C_{max} with a focus on approximation algorithms is presented. Second, we present exact polynomial-time algorithms and approximation algorithms for some subclasses of R||C_{max}. For instance, we present k-approximation algorithms on par with or better than the best known for certain subclasses of R||C_{max}.

No description available.

No description available.

The latest generation of semiconductor wafer fabs produce Integrated Circuits (ICs) on silicon wafers of 300mm diameter. In this dissertation, we address the following two types of (new) scheduling problems that are encountered in this generation of wafer fabs: multiple-lots-per-carrier scheduling problem (MLCSP) and integrated automated material handling and lot scheduling problem (IMHLSP). We consider several variations of the MLCSP depending upon the number of machines used, the prevailing processing technology of the machines, and the type of objective functions involved. For the IMHLSP, we study two instances, one with infinite number of vehicles and the other with finite number of vehicles. We begin by introducing a single-machine, multiple-lots-per-carrier with single-wafer-processing-technology scheduling problem for the objective of minimizing the total completion time (MLCSP1). The wafer carrier is a front-opening unified pod (FOUP) that can hold a limited number of wafers. The problem is easy to solve when all the lots are of the same size. For the case of different lot sizes, we first relax the carrier (FOUP) capacity and propose a dynamic programming-based algorithm, called RelaxFOUP-DP, which enables a quick determination of its optimal solution that serves as a lower bound for the problem with limited FOUP capacity. Then, a branch-and-bound algorithm, designated as MLCSP1-B&B, is developed that relies on the lower bound determined by the RelaxFOUP-DP algorithm. Numerical tests indicate that MLCSP1-B&B finds optimal solutions much faster than the direct solution of the MLCSP1 model by the AMPL CPLEX 10.1 Solver. In fact, for the medium and low density problems, the MLCSP1-B&B algorithm finds optimal solutions at the starting node (node zero) itself. Next, we consider a single-machine, multiple-lots-per-carrier with single-carrier-processing-technology scheduling problem for the objective of minimizing total completion time (MLCSP2). As for the case of MLCSP1, the optimal solution for the case in which all the lots are of the same size can be obtained easily. For the case of different lot sizes, we determine a lower bound and an upper bound for the problem and prove the worst-case ratios for them. Subsequently we analyze a two-machine flow shop, multiple-lots-per-carrier with single-wafer-processing-technology scheduling problem for the objective of minimizing the makespan (MLCSP3). We first consider a relaxed version of this problem, and transform the original problem to a two-machine flow shop lot streaming problem. Then, we propose algorithms to find the optimal capacitated sublot sizes for the case of lots with (1) the same ratio of processing times, and, (2) different ratios of processing times on the machines. Since the optimal solutions obtained from the lot streaming problem may not be feasible to the MLCSP3, we develop heuristic methods based on the heuristic procedures for the bin packing problem. We develop four heuristic procedures for lots with the same ratio of processing times, and another four procedures for lots with different ratios of processing times on the machines. Results of our numerical experimentation are presented that show that our heuristic procedures generate almost optimal solutions in a matter of a few seconds. Next, we address the integrated automated material handling and lot scheduling problem (IMHLSP) in the presence of infinite number of vehicles. We, first, propose a new strong hybrid model, which has the advantages of both segregate and direct models. In the segregate model, a job is always transferred to the stocker after its completion at a station, while in the direct model, it is transferred to the next machine in case that machine can accommodate the jobs; otherwise, the job will stay at current station. The decisions involved in the strong hybrid model are the sequence in which to process the lots and a selection between the segregate and direct models for each lot, whichever optimizes system performance. We show that, under certain conditions about the processing times of the lots, the problem can be approximated by the cases of either infinite buffer or zero-buffer at the machines. Hence, we consider all three cases of the IMHLSP in this chapter, namely, infinite buffer, zero-buffer, and limited buffer sizes. For the strong hybrid model with limited buffer size, we propose a branch-and-bound algorithm, which uses a modified Johnson's algorithm to determine a lower bound. Two upper bounds for this algorithm are also determined. Results of our numerical investigation indicate that our algorithm finds optimal solutions faster than the direct solution of the IMHLSP model by the AMPL CPLEX 10.1 Solver. Experimental results also indicate that for the same problem size, the times required to solve the IMHLSP model with interbay movements are larger than those for intrabay movements. Finally, we investigate the IMHLSP in the presence of limited number of vehicles. Due to the complex nature of the underlying problem, we analyze small-size versions of this problem and develop algorithms for their solution. For some of these problems, we can find optimal solutions in polynomial time. Also, based on our analysis on small-size systems, we have shown why some real-time dispatching (RTD) rules used in real fabs are expected to perform well while not the others. In addition, we also propose some new and promising RTD rules based on our study. / Ph. D.

Yes / Scheduling is an important element that has a major impact on the efficiency of all manufacturing processes. It plays an important role in optimising the manufacturing times and costs resulting in energy efficient processes. It has been estimated that more than 75% of manufacturing processes occur in small batches. In such environments, processes must be able to perform a variety of operations on a mix of different batches. Batch-job scheduling optimisation is the response to such low batch manufacturing problems. The optimisation of batch-job process scheduling problem is still a challenge to researchers and is far from being completely solved due to its combinatorial nature. In this paper, a novel hybrid heuristic (HybH) solution approach for batch-job scheduling problem is presented with the objective of optimising the overall Makespan (Cmax). The proposed HybH is the combination of Index Based Heuristic (IBH) and the Finished Batch-Job (FBJ) process schedule. The heuristic assigns the first operation to a batch-job using IBH and the remaining operations on the basis FBJ process schedule. The FBJ process schedule gives priority to the batch-job with early finished operations, without violating the constraints of process order. The proposed HybH is explained with the help of a detailed example. Several benchmark problems are solved from the literature to check the validity and effectiveness of the proposed heuristic. The presented HybH has achieved batch-job process schedules which have outperformed the traditional heuristics. The results are encouraging and show that the proposed heuristic is a valid methodology for batch process scheduling optimisation.

本研究開發一個以區域最佳解為基礎的群體式 (population-based) 啟發式演算法(簡稱HLBS)，來求解流程式排程（flow shop）之最大流程時間的最小化問題。其中，HLBS會先建置一個跟隨模型來導引搜尋機制，然後，運用過濾策略來預防重複搜尋相同解空間而陷入區域最佳解的困境；但搜尋仍有可能會陷入區域最佳解，這時，HLBS則會啟動跳脫策略來協助跳出區域最佳解，以進入新的區域之搜尋；為驗證HLBS演算法的績效，本研究利用著名的Taillard 測試題庫來進行評估，除證明跟隨模型、過濾策略和跳脫策略的效用外，也提出實驗結果證明HLBS較其他知名群體式啟發式演算法(如基因演算法、蟻群演算法以及粒子群最佳化演算法)之效能為優。 / This research proposes population-based metaheuristic based on the local best solution (HLBS) for the permutation flow shop scheduling problem (PFSP-makespan). The proposed metaheuristic operates through three mechanisms: (i) it introduces a new method to produce a trace-model for guiding the search, (ii) it applies a new filter strategy to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima, and (iii) it initiates a new jump strategy to help the search escape if the search does become trapped at a local optimum. Computational experiments on the well-known Taillard's benchmark data sets will be performed to evaluate the effects of the trace-model generating rule, the filter strategy, and the jump strategy on the performance of HLBS, and to compare the performance of HLBS with all the promising population-based metaheuristics related to Genetic Algorithms (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).

Submitted by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:44:58Z No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:45:05Z (GMT) No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:45:10Z (GMT) No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Made available in DSpace on 2017-08-23T12:45:16Z (GMT). No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) Previous issue date: 2017-02-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The production scheduling activity is considered as one of the most complex activities in production management. This activity is part of the class of NP-Hard problems found in the area of computer science, that is, those problems that can not be solved deterministically in polynomial time. In addition, the complexity of this activity may increase according to the constraints imposed on each programming system/problem. In this research, the problem of programming of production the Flexible Job Shop (JSF) is studied. This problem is considered an extension of the Job Shop programming problem. In JSF, a group of jobs (i.e., products, items, part of an item) formed by a set of operations and each operation must be programmed by a resource (i.e., machine) that belongs to a group of resources that have the same functional characteristics (e.g., cut, sanding, painting). This problem is characterized in two sub-problems being routing and sequencing activity. Routing involves determining which resource will process a given operation. Sequencing is the order in which each operation will be processed on a resource. Through established programming, the objective of this research is to optimize performance multicriteria: the makespan (i.e., time spent to produce a set of jobs), processing time spent on the resource that worked by more time and total production time. In order to reach the objectives mentioned above, a hybrid swarm approach is proposed in this research. In this approach, two auxiliary methods are used to treat the abovementioned sub-problems: genetic operator of mutation to perform the routing activity and for the sequencing activity, an adaptive method of neighborhood structures is proposed. In order to deal with the multiobjectivity of the problem, we propose the Pareto dominance method. Experimental results obtained through commonly used benchmarks prove the efficacy and superiority of the proposed approach when compared to other approaches also applied to the problem studied. / A atividade de programação da produção é considerada como uma das atividades mais complexas no gerenciamento da produção. Essa atividade faz parte da classe de problemas NP-Difícil encontrados na área da ciência da computação, ou seja, aqueles problemas que não podem ser solucionados deterministicamente em tempo polinomial. Além disso, a complexidade dessa atividade pode aumentar de acordo com as restrições impostas a cada sistema/problema de programação. Nesta pesquisa, estuda-se o problema de programação da produção Job Shop Flexível (JSF). Esse problema é considerado como uma extensão do problema de programação Job Shop. No JSF, deve-se programar um grupo de jobs (i.e., produtos, itens, parte de um item) formados por um conjunto de operações e cada operação é processada por um recurso (i.e., máquina) que pertence a um grupo de recursos que possuam mesmas caraterísticas funcionais (e.g., cortar, lixar, pintar). Esse problema é caracterizado em dois sub-problemas, sendo eles, a atividade de roteamento e de sequenciamento. O roteamento implica em definir qual recurso irá processar uma determinada operação. O sequenciamento é a ordem em que cada operação será processada em um recurso. Por meio da programação estabelecida objetiva-se nessa pesquisa, otimizar multicritérios de desempenho, sendo eles: makespan (i.e., tempo gasto para produzir um conjunto de jobs), tempo de processamento gasto no recurso que trabalhou por mais tempo e tempo total de produção. Para alcançar os objetivos supracitados é proposto nessa pesquisa uma abordagem híbrida de enxame de abelhas. Nessa abordagem, utiliza-se dois métodos auxiliares para tratar os sub-problemas supracitados, sendo eles: operador genético de mutação para realizar a atividade de roteamento e para a atividade de sequenciamento é proposto um método adaptativo de estruturas de vizinhança. Para tratar a multiobjetividade do problema, propõe-se o método dominância de Pareto. Resultados experimentais obtidos por meio de benchmarks comumente usados comprovam a eficácia e a superioridade da abordagem proposta quando comparada com outras abordagens também aplicadas ao problema estudado.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-09-21T13:50:00Z No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:27Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:38Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Made available in DSpace on 2016-09-27T19:42:35Z (GMT). No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) Previous issue date: 2015-03-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The generation of Reactive Production Scheduling (PRP) in order to minimize the makespan is an important activity in the manufacturing industry, in view of the numerous articles reflecting this search today. Among these studies highlight the global search use in hybridization or collaboration with local search, especially of Genetic Algorithm (GA) with Variable Neighborhood Search (VNS). But see that the neighborhood structures used are not related to the goal of makespan minimization or when they are, are difficult to obtain. In order to cover this topic, this thesis proposes the hypothesis that a strongly correlated neighborhood structure with objective of makespan minimization in PRP problems, based on spanning tree, and applied on a collaboration among a genetic algorithm with VNS, perform better or equal to those obtained by other studies using other neighborhood structures or without the use of local search. The purpose was to construct a collaboration of GA and VNS using a neighborhood structure based on the mapping of the solution in the spanning tree associated with the problem, in the local search time, and operating with the insert, swap and 2-opt operators. The planning of experiments for validation contemplated since the implementation and comparison of four variants of reactive production scheduling in three job shop scenarios of different sizes. Each pair of comparisons had its calculated sample size and has been tested with the appropriate hypothesis test. The four variants were compared: Genetic Algorithm only and three collaborations of GA with VNS using the neighborhood structure proposal and two other neighborhood structures (Critical Path and Natural Representation) found in the literature review. The scenarios came from Taillard base. The tests corroborate the hypothesis, with 95% confidence, compared to other works and the main contribution of this thesis is to create an efficient method for minimizing makespan in PRP. / A geração de Programação Reativa da Produção (PRP), com o objetivo de minimizar o makespan, é uma atividade importante na indústria manufatureira, tendo em vista os numerosos artigos que abordam esta pesquisa na atualidade. Dentre estas pesquisas, destaca-se o uso de hibridização ou colaboração de busca global com busca local, notadamente de Algoritmo Genético (AG) com Variable Neighborhood Search (VNS). Porém, nota-se que as estruturas de vizinhança utilizadas não são correlatas à função de minimização de makespan ou, quando o são, são de difícil obtenção. Com o intuito de cobrir tal tópico, esta tese propõe a hipótese de que uma estrutura de vizinhança fortemente correlata ao objetivo de minimização de makespan em problemas de PRP, baseando-se em árvore de cobertura e aplicada em uma colaboração de algoritmo genético e VNS, obtém resultados melhores aos obtidos por outros trabalhos, que fazem uso de outras estruturas de vizinhança ou que não utilizam a busca local. A proposta é a construção de um método de colaboração entre AG e VNS usando uma estrutura de vizinhança baseada no mapeamento da solução, em tempo de busca local, na árvore de cobertura associada ao problema, atuando com os operadores insert, swap e 2-opt. O planejamento dos experimentos para validação contempla a execução e comparação de quatro variantes de solução de problemas de Programação Reativa da Produção em três cenários de job shop de diversas dimensões. Cada par de comparações tem seu tamanho amostral calculado e é examinado com o teste de hipótese adequado. As quatro variantes comparadas são: Algoritmo Genético e três colaborações entre Algoritmo Genético e Variable Neighborhood Search (VNS) usando a estrutura de vizinhança proposta e outras duas estruturas de vizinhança (Caminho Crítico e Representação Natural) encontradas na revisão da literatura. Os cenários vem da base Taillard. Os testes corroboram a hipótese com 95% de confiança na comparação com outros trabalhos e a principal contribuição desta tese é a criação de um método eficiente para minimização de makespan em PRP.

Studien genomfördes på industriföretaget Gränges Finspång AB som är en producent av valsade aluminiumprodukter för värmeväxlare vilka används som komponenter främst inom bilindustrin och värme, ventilation och luftkonditionering. Aluminium är en miljöeffektiv råvara tack vare materialets naturliga egenskaper samt dess återanvändbarhet vilket har lett till att allt fler företag vill ta vara på dessa egenskaper vid tillverkning av klimatsmarta produkter. För Gränges Finspång AB har materialets aktualitet på marknaden inneburit en ökad efterfrågan på företagets produkter vilket i sin tur har satt ökad press på företagets produktionseffektivitet. Den produktionsprocess som studerades på företaget var en uppsättning maskiner – även kallade kallvalsverk – vilka kan liknas med en funktionell verkstad. Syftet med studien var att, med hjälp av optimeringsmetoder, ta fram en modell som kan användas som beslutsunderlag för sekvensering av produkter i företagets kallvalsverk. Utifrån intervjuer, granskning av interna dokument och en kvantitativ dataanalys genomfördes en kartläggning av Gränges Finspång AB:s hela produktionsflöde såväl som de processer unika för kallvalsprocessen. För sekvensering av företagets produkter tillämpades en linjär heltalsmodell vilken anger optimum för maximalt 14 produkter. Studien bekräftar att företagets kallvalsning är ett komplext produktionssystem ur ett schemaläggningsperspektiv. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

No description available.