Algorithmic Solutions for Combinatorial Problems in Resource Management of Manufacturing Environments

This thesis studies the use of heuristic algorithms in a number of combinatorial problems that occur in various resource constrained environments. Such problems occur, for example, in manufacturing, where a restricted number of resources (tools, machines, feeder slots) are needed to perform some operations. Many of these problems turn out to be computationally intractable, and heuristic algorithms are used to provide efficient, yet sub-optimal solutions. The main goal of the present study is to build upon existing methods to create new heuristics that provide improved solutions for some of these problems. All of these problems occur in practice, and one of the motivations of our study was the request for improvements from industrial sources. We approach three different resource constrained problems. The first is the tool switching and loading problem, and occurs especially in the assembly of printed circuit boards. This problem has to be solved when an efficient, yet small primary storage is used to access resources (tools) from a less efficient (but unlimited) secondary storage area. We study various forms of the problem and provide improved heuristics for its solution. Second, the nozzle assignment problem is concerned with selecting a suitable set of vacuum nozzles for the arms of a robotic assembly machine. It turns out that this is a specialized formulation of the MINMAX resource allocation formulation of the apportionment problem and it can be solved efficiently and optimally. We construct an exact algorithm specialized for the nozzle selection and provide a proof of its optimality. Third, the problem of feeder assignment and component tape construction occurs when electronic components are inserted and certain component types cause tape movement delays that can significantly impact the efficiency of printed circuit board assembly. Here, careful selection of component slots in the feeder improves the tape movement speed. We provide a formal proof that this problem is of the same complexity as the turnpike problem (a well studied geometric optimization problem), and provide a heuristic algorithm for this problem.

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.

Peliprojektin aikataulutus

Tässä pro gradu -tutkielmassa aikataulutetaan itsenäisen pelinkehittäjän peliprojekti. Aikataulutus on matematiikan ala, jonka tavoitteena on järjestää projektitehtävät optimaaliseen järjestykseen asetetun tavoitteen mukaan. Käytännössä tavoite voi olla esimerkiksi mimimoida painotetun valmistumisajan summaa. Tutkielma koostuu neljästä pääosiosta: aikataulutuksen teoriasta, aikataulutettavan datataulukon muodostuksesta, laskennallisista esimerkeistä ja aikataulutusohjelman esittelystä. Teoriaosuudessa esitetään peliprojektin aikataulutukseen tarvittavat matemaattiset merkinnät ja lemmat todistuksineen. Tutkielman teoriaosuuden todistukset ovat peräisin Michael Pinedon kirjasta Scheduling - Theory, Algorithms, and Systems vuodelta 2008. Pinedon teos on tutkielman keskeisin kirjallisuuslähde. Tutkielman toisessa pääosiossa esitetään, miten peliprojektista saadaan muodostettua aikataulutettava datataulukko. Datataulukon mallinnuksessa apuna toimi turkulainen pelinkehittäjä Timo Naskali. Yhteistyössä Naskalin kanssa peliprojekti saatiin mallinnettua mahdollisimman tarkasti laskettavissa olevaksi datataulukoksi ilman liiallisia yksinkertaistuksia. Peliprojektin mallintamisen lisäksi tutkielmassa tullaan käymään läpi paljon erilaisia esimerkkitehtäviä, joissa sovelletaan esiteltyä teoriaa. Esimerkit on tehty hyvin selkeiksi kirjaamalla ylös paljon laskujen välivaiheita. Esimerkkitehtävien vaikeustaso kasvaa kappaleen edetessä, sillä monimutkaisempia tilanteita tarkasteltaessa datataulukoihin joudutaan lisäämään uusia parametrejä. Viimeisessä esimerkkitehtävässä käytössä on jo koko mallinnettu datataulukko. Tutkielmaa varten koodattiin myös aikataulutusohjelma, joka mahdollistaa isojen datataulukoiden laskemisen tietokoneen avulla. Aikataulutusohjelmassa on graafinen käyttöliittymä, mutta ohjelma tallentaa tulokset myös tekstitiedostoksi. Tutkielman loppuosassa käsitellään aikataulutuksesta saatavaa hyötyä. Johtopäätöksissä pohditaan myös potentiaalisia jatkomahdollisuuksia tutkielman aiheeseen.

Scheduling of guarded command based models

Formal methods provide a means of reasoning about computer programs in order to prove correctness criteria. One subtype of formal methods is based on the weakest precondition predicate transformer semantics and uses guarded commands as the basic modelling construct. Examples of such formalisms are Action Systems and Event-B. Guarded commands can intuitively be understood as actions that may be triggered when an associated guard condition holds. Guarded commands whose guards hold are nondeterministically chosen for execution, but no further control flow is present by default. Such a modelling approach is convenient for proving correctness, and the Refinement Calculus allows for a stepwise development method. It also has a parallel interpretation facilitating development of concurrent software, and it is suitable for describing event-driven scenarios. However, for many application areas, the execution paradigm traditionally used comprises more explicit control flow, which constitutes an obstacle for using the above mentioned formal methods. In this thesis, we study how guarded command based modelling approaches can be conveniently and efficiently scheduled in different scenarios. We first focus on the modelling of trust for transactions in a social networking setting. Due to the event-based nature of the scenario, the use of guarded commands turns out to be relatively straightforward. We continue by studying modelling of concurrent software, with particular focus on compute-intensive scenarios. We go from theoretical considerations to the feasibility of implementation by evaluating the performance and scalability of executing a case study model in parallel using automatic scheduling performed by a dedicated scheduler. Finally, we propose a more explicit and non-centralised approach in which the flow of each task is controlled by a schedule of its own. The schedules are expressed in a dedicated scheduling language, and patterns assist the developer in proving correctness of the scheduled model with respect to the original one.