No description available.

The objective of this thesis is to introduce MES systems with their properties and relations to other automation systems. Furthermore production scheduling theory is introduced with applicable mathematical methods. For given scheduling problem is created optimization model and basic serie of simulations is accomplished. The core of an existing MES system is transformed to web non-comercial platform. All necessary changes are listed in order to integrate production scheduling subsystem to the existing MES system.

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization. * A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. * The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier. * Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception. * ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem. * ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.

The flow shop scheduling problems with fuzzy processing times and fuzzy due dates are investigated in this paper. The concepts of earliness and tardiness are interpreted by using the concepts of possibility and necessity measures that were developed in fuzzy sets theory. And the objective function will be taken into account through the different combinations of possibility and necessity measures. The genetic algorithm will be invoked to tackle these objective functions. A new idea based on longest common substring will be introduced at the best-keeping step. This new algorithm reduces the number of generations needed to reach the stopping criterion. Also, we implement the algorithm on CUDA. The numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU.

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three sub-problems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

no / No / Scheduling systems based on traditional heuristic rules, which deal with the complexities of manufacturing systems, have been used by researchers for the past six decades. These heuristics rules prioritise all jobs that are waiting to be processed on a resource. In this paper, a novel Index Based Heuristic (IBH) solution for the Job Shop Scheduling Problem (JSSP) is presented with the objective of minimising the overall Makespan (Cmax). The JSSP is still a challenge to researchers and is far from being completely solved due to its combinatorial nature. JSSP suits the challenges of current manufacturing environments. The proposed IBH calculates the indices of candidate jobs and assigns the job with the lower index value to the available machine. To minimise the gap between jobs, a swap technique is introduced. The swap technique takes candidate jobs for a machine and swaps them without violating the precedence constraint. Several benchmark problems are solved from the literature to test the validity and effectiveness of the proposed heuristic. The results show that the proposed IBH based algorithm outperforms the traditional heuristics and is a valid methodology for JSSP optimization.

No description available.

No description available.

No description available.

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>