Production lot sizing and scheduling with non-triangular sequence-dependent setup times

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Solving two production scheduling problems with sequence-dependent set-up times

In today’s competitive markets, the importance of goodscheduling strategies in manufacturing companies lead to theneed of developing efficient methods to solve complexscheduling problems.In this paper, we studied two production scheduling problemswith sequence-dependent setups times. The setup times areone of the most common complications in scheduling problems,and are usually associated with cleaning operations andchanging tools and shapes in machines.The first problem considered is a single-machine schedulingwith release dates, sequence-dependent setup times anddelivery times. The performance measure is the maximumlateness.The second problem is a job-shop scheduling problem withsequence-dependent setup times where the objective is tominimize the makespan.We present several priority dispatching rules for bothproblems, followed by a study of their performance. Finally,conclusions and directions of future research are presented.

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.

Sequenciamento de lotes em prensas de alta capacidade com tempo de setup dependente da sequência

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.

Heuristic procedures for solving the General Assembly Line Balancing Problem with Setups (GALBPS)

The General Assembly Line Balancing Problem with Setups (GALBPS) was recently defined in the literature. It adds sequence-dependent setup time considerations to the classical Simple Assembly Line Balancing Problem (SALBP) as follows: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time, thereby providing the task sequence inside each workstation. This paper proposes over 50 priority-rule-based heuristic procedures to solve GALBPS, many of which are an improvement upon heuristic procedures published to date.

Procedimientos de exploración de entornos para la programación de operaciones en una máquina con tiempos de preparación

objetivo de minimizar el retraso total en un ambiente con preparaciones quedependen de la secuencia. Se comparan los resultados obtenidos mediante laaplicación de los procedimientos de exploración de entornos AED, ANED,Recocido Simulado, Algoritmos Genéticos, Búsqueda Tabú y GRASP alproblema planteado. Los resultados sugieren que la Búsqueda Tabú es unatécnica viable de solución que puede proporcionar buenas soluciones cuandose considera el objetivo retraso total con tiempos de preparación dependientesde la secuencia.

Programación de pedidos en una máquina de la vida real con tiempos de preparación dependientes de la secuencia

En este trabajo se evalúan algoritmos heurísticos de exploración de entornos(AED, ANED, SA, TS, GA y GRASP) en la programación de pedidos en unamáquina de la vida real, con el objetivo de minimizar la suma de retrasos . Elcaso estudiado se diferencia de los problemas convencionales en que lostiempos de preparación de las operaciones están separados de los tiempos deprocesamiento y son dependientes de la secuencia. Los resultadoscomputacionales revelan que la Búsqueda Tabú funciona mejor que los otrosalgoritmos aplicados.

Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Cooperative RNA Polymerase Molecules Behavior on a Stochastic Sequence-Dependent Model for Transcription Elongation

The transcription process is crucial to life and the enzyme RNA polymerase (RNAP) is the major component of the transcription machinery. The development of single-molecule techniques, such as magnetic and optical tweezers, atomic-force microscopy and single-molecule fluorescence, increased our understanding of the transcription process and complements traditional biochemical studies. Based on these studies, theoretical models have been proposed to explain and predict the kinetics of the RNAP during the polymerization, highlighting the results achieved by models based on the thermodynamic stability of the transcription elongation complex. However, experiments showed that if more than one RNAP initiates from the same promoter, the transcription behavior slightly changes and new phenomenona are observed. We proposed and implemented a theoretical model that considers collisions between RNAPs and predicts their cooperative behavior during multi-round transcription generalizing the Bai et al. stochastic sequence-dependent model. In our approach, collisions between elongating enzymes modify their transcription rate values. We performed the simulations in Mathematica® and compared the results of the single and the multiple-molecule transcription with experimental results and other theoretical models. Our multi-round approach can recover several expected behaviors, showing that the transcription process for the studied sequences can be accelerated up to 48% when collisions are allowed: the dwell times on pause sites are reduced as well as the distance that the RNAPs backtracked from backtracking sites. © 2013 Costa et al.

Sequence dependent hypermutation of the immunoglobulin heavy chain in cultured B cells

The variable (V) regions of immunoglobulin heavy and light chains undergo high rates of somatic mutation during the immune response. Although point mutations accumulate throughout the V regions and their immediate flanking sequences, analysis of large numbers of mutations that have arisen in vivo reveal that the triplet AGC appears to be most susceptible to mutation. We have stably transfected B cell lines with γ2a heavy chain constructs containing TAG nonsense codons in their V regions that are part of either a putative (T)AGC hot spot or a (T)AGA non-hot spot motif. Using an ELISA spot assay to detect revertants and fluctuation analysis to determine rates of mutation, the rate of reversion of the TAG nonsense codon has been determined for different motifs in different parts of the V region. In the NSO plasma cell line, the (T)AGC hot spot motif mutates at rates of ≈6 × 10−4/bp per generation and ≈3 × 10−5/bp per generation at residues 38 and 94 in the V region. At each of these locations, the (T)AGC hot spot motif is 20–30 times more likely to undergo mutation than the (T)AGA non-hot spot motif. Moreover, the AGA non-hot spot motif mutates at as high a rate as the hot spot motif when it is located adjacent to hot spot motifs, suggesting that more extended sequences influence susceptibility to mutation.

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Heuristics and meta-heuristics for lot sizing and scheduling in the soft drinks industry: A comparison study

This chapter studies a two-level production planning problem where, on each level, a lot sizing and scheduling problem with parallel machines, capacity constraints and sequence-dependent setup costs and times must be solved. The problem can be found in soft drink companies where the production process involves two interdependent levels with decisions concerning raw material storage and soft drink bottling. Models and solution approaches proposed so far are surveyed and conceptually compared. Two different approaches have been selected to perform a series of computational comparisons: an evolutionary technique comprising a genetic algorithm and its memetic version, and a decomposition and relaxation approach. © 2008 Springer-Verlag Berlin Heidelberg.

Reformulação para um problema integrado de dimensionamento e sequenciamento de lotes

In this paper, some new constraints and an extended formulation are presented for a Lot Sizing and Scheduling Model proposed in the literature. In the production process considered a key material is prepared and is transformed into different final items. The sequencing decisions are related to the order in which the materials are processed and the lot sizing decisions are related to the final items production. The mathematical formulation considers sequence-dependent setup costs and times. Results of the computational tests executed using the software Cplex 10.0 showed that the performance of the branch-and-cut method can be improved by the proposed a priori reformulation.

A priori reformulations for joint rolling-horizon scheduling of materials processing and lot-sizing problem

In many production processes, a key material is prepared and then transformed into different final products. The lot sizing decisions concern not only the production of final products, but also that of material preparation in order to take account of their sequence-dependent setup costs and times. The amount of research in recent years indicates the relevance of this problem in various industrial settings. In this paper, facility location reformulation and strengthening constraints are newly applied to a previous lot-sizing model in order to improve solution quality and computing time. Three alternative metaheuristics are used to fix the setup variables, resulting in much improved performance over previous research, especially regarding the use of the metaheuristics for larger instances. © 2013 Elsevier Ltd. All rights reserved.