A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

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)

Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming

This paper addresses the non-preemptive single machine scheduling problem to minimize total tardiness. We are interested in the online version of this problem, where orders arrive at the system at random times. Jobs have to be scheduled without knowledge of what jobs will come afterwards. The processing times and the due dates become known when the order is placed. The order release date occurs only at the beginning of periodic intervals. A customized approximate dynamic programming method is introduced for this problem. The authors also present numerical experiments that assess the reliability of the new approach and show that it performs better than a myopic policy.

Ant colony system based approach to single machine scheduling problems: weighted tardiness scheduling problem

The paper introduces an approach to solve the problem of generating a sequence of jobs that minimizes the total weighted tardiness for a set of jobs to be processed in a single machine. An Ant Colony System based algorithm is validated with benchmark problems available in the OR library. The obtained results were compared with the best available results and were found to be nearer to the optimal. The obtained computational results allowed concluding on their efficiency and effectiveness.

Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.

The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.

Multi-agent system for distributed manufacturing scheduling with genetic algorithms and tabu search

Computerized scheduling methods and computerized scheduling systems according to exemplary embodiments. A computerized scheduling method may be stored in a memory and executed on one or more processors. The method may include defining a main multi-machine scheduling problem as a plurality of single machine scheduling problems; independently solving the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; integrating the plurality of near optimal single machine scheduling problem solutions into a main multi-machine scheduling problem solution; and outputting the main multi-machine scheduling problem solution.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Lot production size problem and simulation of urban transport

OBJECTIVES AND STUDY METHOD: There are two subjects in this thesis: “Lot production size for a parallel machine scheduling problem with auxiliary equipment” and “Bus holding for a simulated traffic network”. Although these two themes seem unrelated, the main idea is the optimization of complex systems. The “Lot production size for a parallel machine scheduling problem with auxiliary equipment” deals with a manufacturing setting where sets of pieces form finished products. The aim is to maximize the profit of the finished products. Each piece may be processed in more than one mold. Molds must be mounted on machines with their corresponding installation setup times. The key point of our methodology is to solve the single period lot-sizing decisions for the finished products together with the piece-mold and the mold-machine assignments, relaxing the constraint that a single mold may not be used in two machines at the same time. For the “Bus holding for a simulated traffic network” we deal with One of the most annoying problems in urban bus operations is bus bunching, which happens when two or more buses arrive at a stop nose to tail. Bus bunching reflects an unreliable service that affects transit operations by increasing passenger-waiting times. This work proposes a linear mathematical programming model that establishes bus holding times at certain stops along a transit corridor to avoid bus bunching. Our approach needs real-time input, so we simulate a transit corridor and apply our mathematical model to the data generated. Thus, the inherent variability of a transit system is considered by the simulation, while the optimization model takes into account the key variables and constraints of the bus operation. CONTRIBUTIONS AND CONCLUSIONS: For the “Lot production size for a parallel machine scheduling problem with auxiliary equipment” the relaxation we propose able to find solutions more efficiently, moreover our experimental results show that most of the solutions verify that molds are non-overlapping even if they are installed on several machines. We propose an exact integer linear programming, a Relax&Fix heuristic, and a multistart greedy algorithm to solve this problem. Experimental results on instances based on real-world data show the efficiency of our approaches. The mathematical model and the algorithm for the lot production size problem, showed in this research, can be used for production planners to help in the scheduling of the manufacturing. For the “Bus holding for a simulated traffic network” most of the literature considers quadratic models that minimize passenger-waiting times, but they are harder to solve and therefore difficult to operate by real-time systems. On the other hand, our methodology reduces passenger-waiting times efficiently given our linear programming model, with the characteristic of applying control intervals just every 5 minutes.

On games corresponding to sequencing situations with precedence relations

In this paper we study a class of cooperative sequencing games that arise from one-machine sequencing situations in which chain precedence relations are imposed on the jobs. It is shown that these sequencing games are convex.

Puristinhuopien pesutehokkuuden vaikutus puristinosan ajettavuuteen

Työn tarkoituksena oli kehittää jatkuvatoimiseen pesuun soveltuva emäksinen ja hapan huovanpesuaine sekä tutkia huovanpesun parametreja laboratoriossa ja paperikoneella. Kirjallisuusosassa tarkasteltiin paperikoneen puristinosaa, puristinhuopien ominaisuuksia, puristinhuovissa esiintyviä saostumia ja puristinhuopien kunnostusta sekä esiteltiin FeltPerm-vedenläpäisykykymittari. Kokeellisessa osassa analysoitiin käytetty huopa kvalitatiivisesti ja kvantitatiivisesti ja kun huopaa tukkivien yhdisteiden kemiallinen luonne oli selvitetty, kehitettiin käynninaikaiseen pesuun soveltuva emäksinen ja hapan huovanpesuaine. Huovanpesuaineiden kehitystyössä pesuaineiden tehokkuutta tutkittiin kolmella eri menetelmällä, joista kaksi perustui huovan massan muutoksen määrittämiseen pesussa ja yksi huovan vedenläpäisykyvyn mittaamiseen. Kehitetyillä pesuaineilla optimoitiin laboratoriossa happo- ja emäspesun pH sekä vaikutusaika. Lisäksi tutkittiin huovan turpoamista emäspesussa ja lämpötilan vaikutusta pesutulokseen. Puristinhuopien vedenläpäisykykyä tutkittiin FeltPerm-laitteella kahdella eri SC-paperikoneella, joista toisella oli käytössä käynninaikainen jaksottainen pesu ja toisella pelkät seisokkipesut. Koneella, jossa huovat pestiin käynninaikaisesti, määritettiin pesuparametreja ja optimoitiin emäsvaiheen aikainen pH. Kehitetyillä pesuaineilla suoritettiin koeajo tehtaalla.

Kemikaalisekoituksen vaikutus kartongin liimausasteen pienimittakaavaiseen vaihteluun

Tässä diplomityössä tutkittiin massaliimauksen stabiilisuutta kartonkikoneella ja himan sekoituskonseptin muuttamisen vaikutusta liimausasteeseen ja liimausasteen pienimittakaavaiseen vaihteluun konerullan sisällä. Koeajoista saadut tulokset olivat erittäin lupaavia. Koeajoissa annosteltiin hartsia kahdella eri TrumpJet™-installaatiolla. Ensimmäisessä koeajossa hartsi sekoitettiin kaikkiin kolmeen kerrokseen sakean massan syöttölinjaan, ennen pyörrepuhdistuksen vaatimaa laimennusta. Toisessa koeajossa hartsi annosteltiin kolmella TrumpJet-suuttimella kartongin pintakerrokseen konesihdin jälkeen ja muihin kerroksiin perinteisesti sekoitussäiliön. Tuloksista nähtiin, että hartsin syöttö perälaatikon lähestymisvirtaukseen on mahdollista kartongin laadun ja liimausasteen siitä karsimatta. Liimausaste määritettiin Stora Enson spesifisen REP-menetelmän (raw edge penetration) avulla. Koesarjojen välille ei syntynyt merkittäviä eroja reunaimeytymätasoihin, eikä koesarjojen sisäisiin vaihteluihin verrattaessa referensikonerulliin.

Optimization and Measuring Techniques for Collect-and-Place Machines in Printed Circuit Board Industry

This thesis considers optimization problems arising in printed circuit board assembly. Especially, the case in which the electronic components of a single circuit board are placed using a single placement machine is studied. Although there is a large number of different placement machines, the use of collect-and-place -type gantry machines is discussed because of their flexibility and increasing popularity in the industry. Instead of solving the entire control optimization problem of a collect-andplace machine with a single application, the problem is divided into multiple subproblems because of its hard combinatorial nature. This dividing technique is called hierarchical decomposition. All the subproblems of the one PCB - one machine -context are described, classified and reviewed. The derived subproblems are then either solved with exact methods or new heuristic algorithms are developed and applied. The exact methods include, for example, a greedy algorithm and a solution based on dynamic programming. Some of the proposed heuristics contain constructive parts while others utilize local search or are based on frequency calculations. For the heuristics, it is made sure with comprehensive experimental tests that they are applicable and feasible. A number of quality functions will be proposed for evaluation and applied to the subproblems. In the experimental tests, artificially generated data from Markov-models and data from real-world PCB production are used. The thesis consists of an introduction and of five publications where the developed and used solution methods are described in their full detail. For all the problems stated in this thesis, the methods proposed are efficient enough to be used in the PCB assembly production in practice and are readily applicable in the PCB manufacturing industry.

Koneinvestointien elinkaarikustannusmalli

Työn tavoitteena oli rakentaa käyttökelpoinen elinkaarikustannusmalli, jonka avulla voidaan arvioida investoitavien uusien koneiden elinkaaren aikaisia kustannuksia. Elinkaarikustannusmalli on rakennettu Microsoft Excel -ohjelman avulla. Mallin tavoitteena oli saada tarkempaa tietoa koneiden aiheuttamista elinkaarikustannuksista. Aiemmin tällaista mallia ei ole ollut käytössä, vaan investointien paremmuutta on paljolti verrattu takaisinmaksuajan ja hankintahinnan perusteella. Työssä hyödynnetään investointi- ja elinkaarilaskennan teorioita elinkaarikustannusmallin rakentamiseen. Työn empiirisessä osiossa käydään läpi, miten elinkaarikustannusmalli on rakennettu ja millaisia ominaisuuksia malli sisältää. Empiirisessä osassa myös testataan rakennetun mallin toimivuutta ja lasketaan elinkaarikustannukset yhdelle koneinvestoinnille. Teoriaosuudessa käsiteltiin myös elinkaarituottoja mallin jatkokehityksen kannalta. Työn tuloksena saatiin rakennettua käyttökelpoinen elinkaarikustannusmalli, jonka ominaisuuksina ovat sen helppo käyttö ja yksinkertaisuus. Mallia voidaan käyttää useammalle koneinvestointivaihtoehdolle samanaikaisesti ja sitä voidaan helposti laajentaa tulevaisuudessa.

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.