Spatial resource allocation is an important consideration in shipbuilding and large-scale manufacturing industries. Spatial scheduling problems (SSP) involve the non-overlapping arrangement of jobs within a limited physical workspace such that some scheduling objective is optimized. Since jobs are heavy and occupy large areas, they cannot be moved once set up, requiring that the same contiguous units of space be assigned throughout the duration of their processing time. This adds an additional level of complexity to the general scheduling problem, due to which solving large instances of the problem becomes computationally intractable. The aim of this study is to gain a deeper understanding of the relationship between the spatial and temporal components of the problem. We exploit these acquired insights on problem characteristics to aid in devising solution procedures that perform well in practice. Much of the literature on SSP focuses on the objective of minimizing the makespan of the schedule. We concentrate our efforts towards the minimum sum of completion times objective and state several interesting results encountered in the pursuit of developing fast and reliable solution methods for this problem. Specifically, we develop mixed-integer programming models that identify groups of jobs (batches) that can be scheduled simultaneously. We identify scenarios where batching is useful and ones where batching jobs provides a solution with a worse objective function value. We present computational analysis on large instances and prove an approximation factor on the performance of this method, under certain conditions. We also provide greedy and list-scheduling heuristics for the problem and compare their objectives with the optimal solution. Based on the instances we tested for both batching and list-scheduling approaches, our assessment is that scheduling jobs similar in processing times within the same space yields good solutions. If processing times are sufficiently different, then grouping jobs together, although seemingly makes a more effective use of the space, does not necessarily result in a lower sum of completion times.

O problema integrado de programação de produção e dimensionamento de lotes em ambiente fowshop consiste em estabelecer tamanhos de lotes de produção e alocar máquinas para processá-los dentro de um horizonte de planejamento, em uma linha de produção com máquinas dispostas em série. O problema considera que a demanda deve ser atendida sem atrasos, que a capacidade das máquinas deve ser respeitada e que as preparações de máquinas são dependentes da sequência de produção e preservadas entre períodos do horizonte de planejamento. O objetivo é determinar uma programação de produção visando minimizar os custos de preparação de máquina, de produção e de estoque. Um modelo matemático da literatura é apresentado assim como procedimentos para obtenção de limitantes inferiores. Além disso, abordamos o problema por meio de distintas versões da metaheurística Times Assíncronos (A-Teams). Os procedimentos propostos foram comparados com heurísticas da literatura baseadas em Programação Inteira Mista (MIP). As metodologias desenvolvidas e os resultados obtidos são apresentados nesta dissertação / The integrated production scheduling and lot sizing problem in a fowshop environment consists in establishing production lot sizes and alocate machines to process them inside a planning horizon, in a production line with machines arranged in series. The problem considers that demand must be met without backlogging, the capacity of the machines must be respected, machine setup are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimize the setup, production and inventory costs. A mathematical model from the literature is presented as well as procedures for obtaining lower bounds. In addition, we propose to address the problem through different versions of the metaheuristic Asynchronous Teams (A-Teams). The procedures were compared with literature heuristics based on Mixed Integer Programming (MIP). The developed methodologies and the obtained results are presented in this dissertation

Este trabalho dedica-se ao problema de programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de execução das tarefas com o objetivo de minimizar a duração total da programação (Makespan). Por intermédio de investigações realizadas sobre as características estruturais do problema de programação e sua solução, uma propriedade deste problema é apresentada. Esta propriedade, denominada \"Propriedade LBY\", considerando quaisquer duas tarefas adjacentes Ju e Jv (Ju imediatamente precede Jv) independentemente de suas posições na seqüência de tarefas, fornece, um limitante inferior do tempo de espera para a tarefa Jv entre o fim do seu processamento na máquina Mk e o início do seu processamento na máquina seguinte. Dois novos métodos heurísticos são desenvolvidos, com base na propriedade apresentada e no procedimento de inserção de tarefas dos conhecidos métodos N&M e NEH: um construtivo, denominado BMc; e, um melhorativo, denominado BMm. Os métodos heurísticos propostos são comparados com os métodos heurísticos melhorativos de Cao; Bedworth (1992) e Rajendran; Ziegler (1997), através de um grande número de problemas gerados aleatoriamente. Os tempos de processamento são distribuídos no intervalo [1, 99] e os tempos de setup nos intervalos de [1, 49], [1, 99], [51, 149] e [101, 199]. Os métodos são avaliados quanto à porcentagem de sucesso em obter a melhor solução, ao desvio relativo médio e o tempo médio de computação. Os resultados da experimentação computacional mostram a qualidade do método construtivo BMc e a melhor performance do método melhorativo BMm. Estes resultados são apresentados e discutidos. / This work addresses the permutation flow shop scheduling problem with separated, non-batch, and sequence-independent setup times with the objective of minimizing the total time to complete the schedule (Makespan). Following an investigation of problem structural characteristics and your solution a property of this scheduling problem is presented. This property, denoted by \"Property LBY\", given any two adjacent jobs Ju e Jv (Ju immediately precedes Jv), regardless of their position in the sequence of jobs, provides an lower bound of the waiting time for job Jv between the end of its operations on the machine Mk and the beginning on machine M(k+1). Two news heuristics methods are development, on the basis of the presented property and in the job insertion procedure of the known methods named N&M and NEH: one constructive, denote by BMc; and, one improvement, denote by BMm. The proposed heuristics methods are compared with the improvement heuristics methods of Cao; Bedworth (1992) and Rajendran; Ziegler (1997), by a large number of randomly generated problems. The processing time are sampled from a distribution ranging from [1, 99] and, the setup times are sampled from distributions ranging from [1, 49], [1, 99], [51, 149] and [101, 199]. The methods are evaluated by the percentage of success in find the best solution, the average relative deviation and the average computation time. The results of the computational investigation show the quality of the constructive heuristic method BMc and that the improvement heuristic method BMc outperforms all others. These results are presented and discussed.

A presente pesquisa tem como objetivo estudar a integração entre dois temas clássicos da literatura de pesquisa operacional e gestão de operações: problemas de corte e empacotamento; e problemas de programação da produção. Ainda que sejam duas áreas intensamente exploradas e pesquisadas, e, ainda, que seja uma situação facilmente encontrada em sistemas de produção reais, abordagens de ambos problemas de forma coordenada ainda carecem de maiores pesquisas. Neste trabalho é feita uma revisão de ambos temas, com foco em problemas de bin packing e programação em ambiente de máquina única com objetivo de minimizar soma de atrasos e adiantamentos ponderados. Uma formulação matemática linear e inteira mista é proposta para o problema, contemplando as restrições que concernem a cada um e também à sua consideração simultânea. Como se trata de um problema que une dois outros, cada um NP-hard isoladamente, um método heurístico é proposto para obter uma solução interessante em tempos computacionais bastante reduzidos. Foram obtidas propriedades físicas de definição de data ideal de programação de um conjunto de itens atribuídos a um bin. Também é proposto um método para geração de um limitante inferior melhorado em relação a pacotes de otimização de mercado para o problema. Ambos métodos foram testados em uma massa de dados de 1.152 instâncias, geradas para retratar cenários de diferentes datas de entrega, setups, custos de atraso e adiantamento em relação à matéria-prima, tamanho de itens e número de itens na instância. Os resultados mostram-se largamente superiores aos obtidos por um otimizador genérico (CPLEX), embora ainda sejam gaps excessivamente grandes, o que reforça a dificuldade do problema. / The present research aims to explore the integration between two classic themes on operations research and operations management literature: cutting and packing problems; and production scheduling problems. Although they are intensive explored and researched areas and, besides, it\'s an easily found situation on real production systems, coordinated approaches of both themes still need deeper research. On this paper, it was done a review of both themes, focusing on bin packing problems and single-machine environment scheduling problems aiming to minimize total weighed earliness and tardiness. A mixed integer-linear mathematical formulation is proposed to the problem, including constraints referred to each problem and, also, to their simultaneous consideration. Once it\'s a problem that joins the other two, each one NP-hard solely, an heuristic method is proposed to obtain an interesting solution in reasonable computational times. Physical properties were identified, defining the best date to allocate a given lot of items to be processed together. Also, a lower bound generation method is proposed, improving the one generated by optimization softwares. Both methods were tested on a 1.152 instances mass of data, generated to represent well several scenarios of different due dates, setup times, earliness and tardiness costs compared to raw material, size of items and number the items the instance. Results show largely superiority the ones obtained by an optimization pack (CPLEX), although gaps are still excessively large, fact the reinforces problem\'s difficulty.

Ngo-Tai Fong. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 158-168). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Manufacturing Systems: An Overview --- p.1 / Chapter 1.2 --- Previous Research --- p.3 / Chapter 1.3 --- Motivation --- p.5 / Chapter 1.4 --- Outline of the Thesis --- p.8 / Chapter 2 --- Preliminaries --- p.11 / Chapter 2.1 --- Problem Formulation: Deterministic Production Planning --- p.11 / Chapter 2.2 --- Markov Chain --- p.15 / Chapter 2.3 --- Problem Formulation: Stochastic Production Planning --- p.18 / Chapter 2.4 --- Some Lemmas --- p.24 / Chapter 3 --- Open-Loop Production Planning in Stochastic Flowshops --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- Limiting Problem --- p.29 / Chapter 3.3 --- Weak-Lipschitz Continuity --- p.34 / Chapter 3.4 --- Constraint Domain Approximation --- p.41 / Chapter 3.5 --- Asymptotic Analysis: Initial States in Sε --- p.47 / Chapter 3.6 --- Asymptotic Analysis: Initial States in S \ Sε --- p.61 / Chapter 3.7 --- Concluding Remarks --- p.70 / Chapter 4 --- Feedback Production Planning in Deterministic Flowshops --- p.72 / Chapter 4.1 --- Introduction --- p.72 / Chapter 4.2 --- Assumptions --- p.75 / Chapter 4.3 --- Optimal Feedback Controls --- p.76 / Chapter 4.3.1 --- The Case c1 < c2+ --- p.78 / Chapter 4.3.2 --- The Case c1 ≥ c2+ --- p.83 / Chapter 4.4 --- Concluding Remarks --- p.88 / Chapter 5 --- Feedback Production Planning in Stochastic Flowshops --- p.90 / Chapter 5.1 --- Introduction --- p.90 / Chapter 5.2 --- Original and Limiting Problems --- p.91 / Chapter 5.3 --- Asymptotic Optimal Feedback Controls for pε --- p.97 / Chapter 5.3.1 --- The Case c1 < c2+ --- p.97 / Chapter 5.3.2 --- The Case c1 ≥ c2+ --- p.118 / Chapter 5.4 --- Concluding Remarks --- p.124 / Chapter 6 --- Computational Evaluation of Hierarchical Controls --- p.126 / Chapter 6.1 --- Introduction --- p.126 / Chapter 6.2 --- The Problem and Control Policies under Consideration --- p.128 / Chapter 6.2.1 --- The Problem --- p.128 / Chapter 6.2.2 --- Hierarchical Control (HC) --- p.131 / Chapter 6.2.3 --- Kanban Control (KC) --- p.133 / Chapter 6.2.4 --- Two-Boundary Control (TBC) --- p.137 / Chapter 6.2.5 --- "Similarities and Differences between HC, KC, and TBC" --- p.141 / Chapter 6.3 --- Computational Results --- p.142 / Chapter 6.4 --- Comparison of HC with Other Polices --- p.145 / Chapter 6.5 --- Concluding Remarks --- p.151 / Chapter 7 --- Conclusions and Future Research --- p.153 / Bibliography --- p.158

by Lam Shiu-chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 107-113). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Task Scheduling Problem and Lower Bound --- p.3 / Chapter 1.3 --- Organization of the Thesis --- p.4 / Chapter 2 --- Teamwork-Task Scheduling Problem --- p.5 / Chapter 2.1 --- Problem Statement and Notations --- p.5 / Chapter 2.2 --- Classification of Scheduling --- p.7 / Chapter 2.3 --- Computational Complexity --- p.9 / Chapter 2.4 --- Literature Review --- p.12 / Chapter 2.4.1 --- Unrelated Machines Scheduling Environment --- p.12 / Chapter 2.4.2 --- Multiprocessors Scheduling Problem --- p.13 / Chapter 2.4.3 --- Search Algorithms --- p.14 / Chapter 2.4.4 --- Lower Bounds --- p.15 / Chapter 2.5 --- Summary --- p.17 / Chapter 3 --- Fundamentals of Genetic Algorithms --- p.18 / Chapter 3.1 --- Initial Inspiration --- p.18 / Chapter 3.2 --- An Elementary Genetic Algorithm --- p.20 / Chapter 3.2.1 --- "Genes, Chromosomes and Representations" --- p.20 / Chapter 3.2.2 --- Population Pool --- p.22 / Chapter 3.2.3 --- Evaluation Module --- p.22 / Chapter 3.2.4 --- Reproduction Module --- p.22 / Chapter 3.2.5 --- Genetic Operators: Crossover and Mutation --- p.23 / Chapter 3.2.6 --- Parameters --- p.24 / Chapter 3.3 --- A Brief Note to the Background Theory --- p.25 / Chapter 3.4 --- Key Factors for the Success --- p.27 / Chapter 4 --- Tasks Scheduling using Genetic Algorithms --- p.28 / Chapter 4.1 --- Details of Scheduling Problem --- p.28 / Chapter 4.2 --- Chromosome Coding --- p.32 / Chapter 4.2.1 --- Job Priority Sequence --- p.33 / Chapter 4.2.2 --- Engineer Priority Sequence --- p.33 / Chapter 4.2.3 --- An Example Chromosome Interpretation --- p.34 / Chapter 4.3 --- Fitness Evaluation --- p.37 / Chapter 4.4 --- Parent Selection --- p.38 / Chapter 4.5 --- Genetic Operators and Reproduction --- p.40 / Chapter 4.5.1 --- Job Priority Crossover (JOB-CRX) --- p.40 / Chapter 4.5.2 --- Job Priority Mutation (JOB-MUT) --- p.40 / Chapter 4.5.3 --- Engineer Priority Mutation (ENG-MUT) --- p.42 / Chapter 4.5.4 --- Reproduction: New Population --- p.42 / Chapter 4.6 --- Replacement Strategy --- p.43 / Chapter 4.7 --- The Complete Genetic Algorithm --- p.44 / Chapter 5 --- Lower Bound on Optimal Makespan --- p.46 / Chapter 5.1 --- Introduction --- p.46 / Chapter 5.2 --- Definitions and Assumptions --- p.48 / Chapter 5.2.1 --- Task Graph --- p.48 / Chapter 5.2.2 --- Graph Partitioning --- p.49 / Chapter 5.2.3 --- Activity and Load Density --- p.51 / Chapter 5.2.4 --- Assumptions --- p.52 / Chapter 5.3 --- Concepts of Lower Bound on the Minimal Time (LBMT) --- p.53 / Chapter 5.3.1 --- Previous Bound (LBMTF) --- p.53 / Chapter 5.3.2 --- Bound in other form --- p.54 / Chapter 5.3.3 --- Improved Bound (LBMTJR） --- p.56 / Chapter 5.4 --- Lower bound: Task graph reconstruction + LBMTJR --- p.59 / Chapter 5.4.1 --- Problem reduction and Assumptions --- p.60 / Chapter 5.4.2 --- Scenario I --- p.61 / Chapter 5.4.3 --- Scenario II --- p.63 / Chapter 5.4.4 --- An Example --- p.67 / Chapter 6 --- Computational Results and Discussions --- p.73 / Chapter 6.1 --- Parameterization of the GA --- p.73 / Chapter 6.2 --- Computational Results --- p.75 / Chapter 6.3 --- Performance Evaluation --- p.81 / Chapter 6.3.1 --- Solution Quality --- p.81 / Chapter 6.3.2 --- Computational Complexity --- p.86 / Chapter 6.4 --- Effects of Machines Eligibility --- p.88 / Chapter 6.5 --- Future Direction --- p.90 / Chapter 7 --- Conclusion --- p.92 / Chapter A --- Tasks data of problem sets in section 6.2 --- p.94 / Chapter A.l --- Problem 1: 19 tasks --- p.95 / Chapter A.2 --- Problem 2: 21 tasks --- p.97 / Chapter A.3 --- Problem 3: 19 tasks --- p.99 / Chapter A.4 --- Problem 4: 23 tasks --- p.101 / Chapter A.5 --- Problem 5: 27 tasks --- p.104 / Bibliography --- p.107

by Chu Kwok-Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 91-93). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Ordinary Dispatching Policies --- p.5 / Chapter 1.2.2 --- Setup-oriented Dispatching Policies --- p.7 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Slack Based Policies --- p.11 / Chapter 2.1 --- Definition of Slack --- p.12 / Chapter 2.2 --- Least Slack Policy (LS) --- p.13 / Chapter 2.3 --- Least Weighted Slack Policy (LWS) --- p.15 / Chapter 2.3.1 --- Definition of Weighted Slack --- p.15 / Chapter 2.3.2 --- Policy Mechanism and Discussion --- p.15 / Chapter 2.4 --- Least Mean Slack Policy (LMS) --- p.16 / Chapter 2.4.1 --- Batch Size and Its Lower Bound --- p.16 / Chapter 2.4.2 --- Policy Mechanism and Discussion --- p.17 / Chapter 2.5 --- Least Weighted Mean Slack Policy (LWMS) --- p.18 / Chapter 2.5.1 --- Definition of Weighted Mean Slack --- p.18 / Chapter 2.5.2 --- Policy Mechanism and Discussion --- p.18 / Chapter 2.6 --- Illustrative Example --- p.21 / Chapter 2.7 --- Due-date Window Expansion --- p.24 / Chapter 2.7.1 --- Due-date Window --- p.24 / Chapter 2.7.2 --- LWMS Policy: Due Date Window Expansion --- p.25 / Chapter 3 --- Simulation Study --- p.27 / Chapter 3.1 --- Models Description --- p.27 / Chapter 3.1.1 --- Two-Machines-Two-Products Model --- p.27 / Chapter 3.1.2 --- Assembly Lines Model --- p.29 / Chapter 3.1.3 --- Micro-Chips Testing Model --- p.31 / Chapter 3.2 --- Simulation Experiment Description --- p.32 / Chapter 4 --- Simulation Result and Analysis --- p.38 / Chapter 4.1 --- Simulation Result --- p.39 / Chapter 4.1.1 --- Two-Machines-Two-Products Model --- p.39 / Chapter 4.1.2 --- Assembly Lines Model --- p.39 / Chapter 4.1.3 --- Micro-Chips Testing Model --- p.43 / Chapter 4.2 --- Statistical Analysis --- p.44 / Chapter 4.2.1 --- Significance of Weighted Factor and Batch Size --- p.44 / Chapter 4.2.2 --- Comparison Among Different Policies --- p.46 / Chapter 4.3 --- Discussion of Results --- p.50 / Chapter 5 --- An Experimental Implementation and Conclusion Remarks --- p.51 / Chapter A --- Reducing MCT and SDCT by LS policy --- p.55 / Chapter A.1 --- Reducing Variance of Lateness --- p.55 / Chapter A.2 --- Reducing Variance of Cycle Time --- p.56 / Chapter A.3 --- Reducing Mean Cycle Time --- p.56 / Chapter B --- Complete Simulation Result --- p.58 / Chapter B.1 --- Two-Machines-Two-Products Model --- p.58 / Chapter B.1.1 --- "Wip, Batch Size and Throughput" --- p.58 / Chapter B.1.2 --- MCT and SDCT --- p.62 / Chapter B.1.3 --- Machine Utilization --- p.66 / Chapter B.2 --- Assembly Lines Model --- p.68 / Chapter B.2.1 --- "WIP, Batch Size and Throughput" --- p.68 / Chapter B.2.2 --- MCT and SDCT --- p.70 / Chapter B.2.3 --- Machine Utilization --- p.73 / Chapter B.3 --- Micro-Chips Testing Model --- p.82 / Chapter B.3.1 --- "WIP, Throughput, MCT and SDCT" --- p.82 / Chapter B.3.2 --- Machine Utilization --- p.84 / Chapter C --- MANOVA studies on Weighted Factor and Batch Size --- p.86 / Chapter C.1 --- Two-Machines-Two-Products Model --- p.86 / Chapter C.1.1 --- Least Weighted Slack Policy --- p.86 / Chapter C.1.2 --- Least Mean Slack Policy --- p.87 / Chapter C.1.3 --- Least Weighted Mean Slack Policy --- p.87 / Chapter C.2 --- Assembly Lines Model --- p.88 / Chapter C.2.1 --- Least Weighted Slack Policy --- p.88 / Chapter C.2.2 --- Least Mean Slack Policy --- p.88 / Chapter C.2.3 --- Least Weighted Mean Slack Policy --- p.89 / Chapter C.3 --- Micro-Chips Testing Model --- p.89 / Chapter C.3.1 --- Least Weighted Slack Policy --- p.89 / Chapter C.3.2 --- Least Mean Slack Policy --- p.90 / Chapter C.3.3 --- Least Weighted Mean Slack Policy --- p.90 / Bibliography --- p.91

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND AERO. / Bibliography: leaves 105-108. / by Herve J-M Duchesne de Lamotte. / M.S.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND AERO. / Bibliography: leaves 175-176. / by Bruce Curtis Lubow. / M.S.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.