Spelling suggestions: "subject:"mixedinteger linear programming model"" "subject:"biginteger linear programming model""
1 |
Modeling and Optimizing of Integrated Multi-Modal Energy Systems for Municipal Energy UtilitiesScheller, Fabian 05 June 2019 (has links)
The development of sustainable business models is a challenging task since various factors might influence the results of an assessment. Given the complexity at the municipal level, system interdependencies between different alternatives need to be considered. One possibility to support decision makers is to apply energy system optimization models. Existing optimization models, however, ignore the roles different actors play and the resulting impact they have.
To address this research issue, this thesis presents an integrated techno-economic optimization framework called IRPopt (Integrated Resource Planning and Optimization). A proven graph-based energy system approach allows the accurate modeling of deployment systems by considering different energy carriers and technical processes. In addition, a graph-based commercial association approach enables the integration of actor-oriented coordination. This is achieved by the explicit modeling of market actors on one layer and technology processes on another layer as well as resource flow interrelations and commercial agreements mechanism among and between the different layers. Using the optimization framework, various optimization problems are solvable on the basis of a generic objective function.
For demonstration purposes, this thesis assesses the business models demand response and community storage. The applied examples demonstrate the modeling capabilities of the developed optimization framework. Further, the dispatch results show the usefulness of the described optimization approach.
|
2 |
Problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados. / Fleet size and mix vehicle routing problem with time windows and scaled costs.Manguino, João Luiz Veiga 18 February 2013 (has links)
O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.
|
3 |
Επιλογή και αξιολόγηση προμηθευτών στην εφοδιαστική αλυσίδα και βελτιστοποίησή τουςΒαγενάς, Δημήτριος 20 May 2013 (has links)
Στην παρούσα διπλωματική μελέτη, σχεδιάζεται και αναπτύσσεται ένα αξιόπιστο σύστημα βαθμολόγησης και άρα αξιολόγησης των προμηθευτών απαραίτητων σε μία Εφοδιαστική Αλυσίδα Αγαθών και Υπηρεσιών.
Η μεθοδολογία περιλαμβάνει: Καθορισμό Ομάδας Αξιολόγησης, Ταξινόμηση Εφοδιαστικών Απαιτήσεων (Supply Positioning) σε υλικά και υπηρεσίες (υψηλής κερδοφορίας, κρίσιμα, μη κρίσιμα, στρατηγικής σημασίας, χαμηλού κόστους & υψηλού κινδύνου), Κατάσταση Κρίσιμων Υλικών και Υπηρεσιών, Επισήμανση Δυνητικών Προμηθευτών, Προεπιλογή Προμηθευτών, Συνεργασία - Συζήτηση με Προμηθευτές, Προσδιορισμό Κριτηρίων επιλογής Προμηθευτών, Συντελεστές Βαρύτητας Κριτηρίων, Ανάπτυξη Ανάλυσης SWOT, Έρευνα για επί πλέον πληροφορίες, Σύνταξη και αποστολή Ερωτηματολογίου – Επεξεργασία, Βαθμολογία Δυνητικών Προμηθευτών, Τήρηση Αρχείου Εγκεκριμένων Προμηθευτών.
Εν συνεχεία γίνεται μία επισκόπηση τεσσάρων-πέντε κύριων μεθόδων επιλογής και μία βιβλιογραφική ανασκόπηση των ερευνητικών προσπαθειών. Παρουσιάζονται αναλυτικά τα κριτήρια απόφασης, οι μέθοδοι επιλογής (εξάλειψης ή βελτιστοποίησης), τα χαρακτηριστικά του προβλήματος επιλογής προμηθευτή (στρατηγική απόφαση, συνενωτικοί κανόνες, πολλαπλοί εμπλεκόμενοι-παίκτες & διαμορφωτές λήψης απόφασης, πολλαπλά αντικειμενικά και υποκειμενικά κριτήρια, περιορισμοί τόσο των προμηθευτών όσο και της εταιρείας, και ο πιθανοκρατικός χαρακτήρας του προβλήματος) .
Η προσέγγιση απαιτεί η απόφαση να ληφθεί σε δύο στάδια.
Στο πρώτο στάδιο, επιλέγουμε τους στρατηγικούς προμηθευτές διαμέσου της εταιρικής στρατηγικής για να επιλεχθούν οι προμηθευτές εκείνοι που εγγυώνται την μακροπρόθεσμη βιωσιμότητα της εταιρείας και το ελάχιστο κατώφλι κάθε κριτηρίου.
Στο δεύτερο στάδιο της προσέγγισης αυτής, προτείνεται ένα γραμμικό μοντέλο μικτού ακέραιου προγραμματισμού για να επιλεγούν οι καλύτεροι προμηθευτές και οι απαιτούμενες ποσότητες θεωρώντας τους περιορισμούς τόσο των προμηθευτών όσο και της επιχείρησης. Ο σκοπός αυτού του μοντέλου είναι να μεγιστοποιηθεί η συνάρτηση U που αναπαριστά τον ολικό βαθμό που δίνεται από την ομάδα απόφασης. Προτείνεται ένας τρόπος για να ληφθεί υπόψη η πιθανοκρατική συμπεριφορά των υποψήφιων προμηθευτών. Τέλος, για καλύτερη κατανόηση, παρουσιάζεται ένα αριθμητικό παράδειγμα βελτιστοποίησης α) χωρίς περιορισμούς με την προσέγγιση της μεθόδου Αναλυτικής Ιεράρχησης (AHP) και β) με περιορισμούς. Το παράδειγμα μας δείχνει ότι η μαθηματική προσέγγιση ήταν η καλύτερη μέθοδος η οποία λαμβάνει υπόψη όλους τους περιορισμούς. / In this thesis study, it is designed and developed a reliable system calibration and evaluation of suppliers so necessary in a Supply Chain of Goods and Services.
The methodology includes: Evaluation Team Specification, Supply Requirements Sorting (Supply Positioning) for materials and services (high profitability, critical, non-critical, strategic, low cost & high risk), Critical Materials and Services Condition, Potential suppliers Highlight, Suppliers Pre-selection, Cooperation - Discussion with Suppliers, Vendor Selection Criteria Identification,, Criteria Weight Credits, SWOT Analysis Development, Research for additional information, Writing, Editing and sending questionnaires, Potential suppliers Review, Approved Suppliers File Records (Archives).
An overview of four to five core selection methods and a literature review of research efforts are following. The decision criteria, the selection methods (optimization or elimination) and the characteristics of the supplier selection problem (strategic decision, conjunctive rules, multiple stakeholders-players & decision makers, multiple objective and subjective criteria, constraints regarding to suppliers and the company, the probabilistic nature of the problem) are presenting in details.
This approach requires a decision taken in two stages.
In the first stage, we select strategic suppliers through the corporate strategy in order to select those suppliers that guarantee the long term viability of the company and the minimum threshold for each criterion.
In the second stage of this approach, it is proposed a mixed-integer linear programming model to select the best suppliers and the required quantities considering the limitations of suppliers and the business as well. The purpose of this model is to maximize the function U representing the overall degree given by the group decision. It is also proposed a way to take into account the probabilistic behavior of supply candidates. Finally, for better understanding, a numerical example of optimization is presented a) without restrictions with the approach of Analytic Hierarchy process (AHP) and b) with restrictions. The example shows that the mathematical approach was the best method which takes into account all the constraints.
|
4 |
Problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados. / Fleet size and mix vehicle routing problem with time windows and scaled costs.João Luiz Veiga Manguino 18 February 2013 (has links)
O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.
|
5 |
Batch Processsor Scheduling - A Class Of Problems In Steel Casting FoundriesRamasubramaniam, M 06 1900 (has links)
Modern manufacturing systems need new types of scheduling methods. While traditional scheduling methods are primarily concerned with sequencing of jobs, modern manufacturing environments provide the additional possibility to process jobs in batches. This adds to the complexity of scheduling. There are two types of batching namely: (i) serial batching (jobs may be batched if they share the same setup on a machine and one job is processed at a time. The machine which processes jobs in this manner is called as discrete processor) and (ii) parallel batching (several jobs can be processed simultaneously on a machine at a time. The machine which processes jobs in this manner is called as batch processor or batch processing machine).
Parallel batching environments have attracted wide attention of the researchers working in the field of scheduling. Particularly, taking inspiration from studies of scheduling batch processors in semiconductor manufacturing [Mathirajan and Sivakumar (2006b) and Venkataramana (2006)] and in steel casting industries [Krishnaswamy et al. (1998), Shekar (1998) and Mathirajan (2002)] in the Management Studies Department of Indian Institute of Science, this thesis addresses a special problem on scheduling batch processor, observed in the steel casting manufacturing.
A fundamental feature of the steel casting industry is its extreme flexibility, enabling castings to be produced with almost unlimited freedom in design over an extremely wide range of sizes, quantities and materials suited to practically every environment and application. Furthermore, the steel casting industry is capital intensive and highly competitive.
From the viewpoint of throughput and utilization of the important and costly resources in the foundry manufacturing, it was felt that the process-controlled furnace operations for the melting and pouring operations as well as the heat-treatment furnace operations are critical for meeting the overall production schedules. The two furnace operations are batch processes that have distinctive constraints on job-mixes in addition to the usual capacity and technical constraints associated with any industrial processes. The benefits of effective scheduling of these batch processes include higher machine utilization, lower work-in-process (WIP) inventory, shorter cycle time and greater customer satisfaction [Pinedo (1995)].
Very few studies address the production planning and scheduling models for a steel foundry, considering the melting furnace of the pre-casting stage as the core foundry operation [Voorhis et al. (2001), Krishnaswamy et al. (1998) and Shekar (1998)]. Even though the melting and pouring operations may be considered as the core of foundry operations and their scheduling is of central importance, the scheduling of heat-treatment furnaces is also of considerable importance. This is because the processing time required at the heat treatment furnace is often longer compared to other operations in the steel-casting foundry and therefore considerably affects the scheduling, overall flow time and WIP inventory.
Further, the heat-treatment operation is critical because it determines the final properties that enable components to perform under demanding service conditions such as large mechanical load, high temperature and anti-corrosive processing. It is also important to note that the heat-treatment operation is the only predominantly long process in the entire steel casting manufacturing process, taking up a large part of total processing time (taking up to a few days as against other processes that typically take only a few hours). Because of these, the heat-treatment operation is a major bottleneck operation in the entire steel casting process.
The jobs in the WIP inventory in front of heat-treatment furnace vary widely in sizes (few grams to a ton) and dimensions (from 10 mm to 2000 mm). Furthermore, castings are primarily classified into a number of job families based on the alloy type, such as low alloy castings and high alloy castings. These job families are incompatible as the temperature requirement for low alloy and high alloy vary for similar type of heat-treatment operation required. These job families are further classified into various sub-families based on the type of heat treatment operations they undergo. These sub-families are also incompatible as each of these sub-families requires a different combination of heat-treatment operation. The widely varying job sizes, job dimensions and multiple incompatible job family characteristic introduce a high degree of complexity into scheduling heat-treatment furnace.
Scheduling of heat-treatment furnace with multiple incompatible job families can have profound effect on the overall production rate as the processing time at heat-treatment operation is very much longer. Considering the complexity of the process and time consumed by the heat treatment operation, it is imperative that efficient scheduling of this operation is required in order to maximize throughput and to enhance productivity of the entire steel casting manufacturing process. This is of importance to the firm. The concerns of the management in increasing the throughput of the bottleneck machine, thereby increasing productivity, motivated us to adopt the scheduling objective of makespan.
In a recent observation of heat-treatment operations in a couple of steel casting industries and the research studies reported in the literature, we noticed that the real-life problem of dynamic scheduling of heat-treatment furnace with multiple incompatible job families, non-identical job sizes, non-identical job dimensions, non-agreeable release times and due dates to maximize the throughput, higher utilization and minimize the work-in-process inventory is not at all addressed. However, there are very few studies [Mathirajan et al. (2001, 2002, 2004a, 2007)] which have addressed the problem of scheduling of heat-treatment furnace with incompatible job families and non-identical job sizes to maximize the utilization of the furnace. Due to the difference between the real-life situation on dynamic scheduling of heat-treatment furnace of the steel casting manufacturing and the research reported on the same problem, we identified three new class of batch processor problems, which are applicable to a real-life situation based on the type of heat-treatment operation(s) being carried out and the type of steel casting industry (small, medium and large scale steel casting industry) and this thesis addresses these new class of research problems on scheduling of batch processor.
The first part of the thesis addresses our new Research Problem (called Research Problem 1) of minimizing makespan (Cmax) on a batch processor (BP) with single job family (SJF), non-identical job sizes (NIJS), and non-identical job dimensions (NIJD). This problem is of interest to small scale steel casting industries performing only one type of heat treatment operation such as surface hardening. Generally, there would be only a few steel casting industries which offer such type of special heat-treatment operation and thus the customer is willing to accept delay in the completion of his orders. So, the due date issues are not important for these types of industries.
We formulate the problem as Mixed Integer Linear Programming (MILP) model and validate the proposed MILP model through a numerical example. In order to understand the computational intractability issue, we carry out a small computational experiment. The results of this experiment indicate that the computational time required, as a function of problem size, for solving the MILP model is non-deterministic and non-polynomial.
Due to the computational intractability of the proposed MILP model, we propose five variants of a greedy heuristic algorithm and a genetic algorithm for addressing the Research Problem 1. We carry out computational experiments to obtain the performance of heuristic algorithms based on two perspectives: (i) comparison with optimal solution on small scale instances and (ii) comparison with lower bound for large scale instances. We choose five important problem parameters for the computational experiment and propose a suitable experimental design to generate pseudo problem instances.
As there is no lower bound (LB) procedure for the Research Problem1, in this thesis, we develop an LB procedure that provides LB on makespan by considering both NIJS and NIJD characteristics together. Before using the proposed LB procedure for evaluating heuristic algorithms, we conduct a computational experiment to obtain the quality of the LB on makespan in comparison with optimal makespan on number of small scale instances. The results of this experiment indicate that the proposed LB procedure is efficient and could be used to obtain LB on makespan for any large scale problem.
In the first perspective of the evaluation of the performance of the heuristic algorithms proposed for Research Problem 1, the proposed heuristic algorithms are run through small scale problem instances and we record the makespan values. We solve the MILP model to obtain optimal solutions for these small scale instances. For comparing the proposed heuristic algorithms we use the performance measures: (a) number of times the proposed heuristic algorithm solution equal to optimal solution and (b) average loss with respect to optimal solution in percentage.
In the second perspective of the evaluation of the performance of the heuristic algorithms, the proposed heuristic algorithms are run through large scale problem instances and we record the makespan values. The LB procedure is also run through these problem instances to obtain LB on makespan. For comparing the performance of heuristic algorithms with respect to LB on makespan, we use the performance measures: (a) number of times the proposed heuristic algorithm solution equal to LB on makespan (b) average loss with respect to LB on makespan in percentage, (c) average relative percentage deviation and (d) maximum relative percentage deviation.
We extend the Research Problem 1 by including additional job characteristics: job arrival time to WIP inventory area of heat-treatment furnace, due date and additional constraint on non-agreeable release time and due date (NARD). Due date considerations and the constraint on non-agreeable release times and due date (called Research Problem 2) are imperative to small scale steel casting foundries performing traditional but only one type of heat treatment operation such as annealing where due date compliance is important as many steel casting industries offer such type of heat treatment operations. The mathematical model, LB procedure, greedy heuristic algorithm and genetic algorithm proposed for Research Problem 1, including the computational experiments, are appropriately modified and\or extended for addressing Research Problem 2.
Finally, we extend the Research Problem 2 is by including an additional real life dimension: multiple incompatible job families (MIJF). This new Research Problem (called Research Problem 3) is more relevant to medium and large scale steel casting foundries performing more than one type of heat treatment operations such as homogenizing and tempering, normalizing and tempering. The solution methodologies, the LB procedure and the computational experiments proposed for Research Problem 2 are further modified and enriched to address the Research Problem 3.
From the detailed computational experiments conducted for each of the research problems defined in this study, we observe that: (a) the problem parameters considered in this study have influence on the performance of the heuristic algorithms, (b) the proposed LB procedure is found to be efficient, (c) the proposed genetic algorithm outperforms among the proposed heuristic algorithms (but the computational time required for genetic algorithm increases as problem size keeps increasing), and (d) in case the decision maker wants to choose an heuristic algorithm which is computationally most efficient algorithm among the proposed algorithms, the variants of greedy heuristic algorithms : SWB, SWB(NARD), SWB(NARD&MIJF) is relatively the best algorithm for Research Problem 1, Research Problem 2 and Research Problem 3 respectively.
|
Page generated in 0.1231 seconds