Search results for: heuristic solution

Authors: Hanife Merve Öztürk, Sıdıka Dalgan

Abstract:

In this project, a capacity analysis study is done at TAT A. Ş. Maret Plant. Production capacity of products which generate 80% of sales amount are determined. Obtained data entered the LEKIN Scheduling Program and we get production schedules by using heuristic methods. Besides heuristic methods, as mathematical model, disjunctive programming formulation is adapted to flexible job shop problems by adding a new constraint to find optimal schedule solution.

Keywords: scheduling, flexible job shop problem, shifting bottleneck heuristic, mathematical modelling

Procedia PDF Downloads 366

Authors: Kamaljit Pati, Manas Kumar Mohanty, Sanjib Sadhu

Abstract:

A heuristic has been designed to generate a random simple monotone polygon from a given set of ‘n’ points lying on a 2-Dimensional plane. Our heuristic generates a random monotone polygon in O(n) time after O(nℓogn) preprocessing time which is improved over the previous work where a random monotone polygon is produced in the same O(n) time but the preprocessing time is O(k) for n < k < n2. However, our heuristic does not generate all possible random polygons with uniform probability. The space complexity of our proposed heuristic is O(n).

Keywords: sorting, monotone polygon, visibility, chain

Procedia PDF Downloads 398

Authors: Nicolas Zufferey

Abstract:

Ant algorithms are well-known metaheuristics which have been widely used since two decades. In most of the literature, an ant is a constructive heuristic able to build a solution from scratch. However, other types of ant algorithms have recently emerged: the discussion is thus not limited by the common framework of the constructive ant algorithms. Generally, at each generation of an ant algorithm, each ant builds a solution step by step by adding an element to it. Each choice is based on the greedy force (also called the visibility, the short term profit or the heuristic information) and the trail system (central memory which collects historical information of the search process). Usually, all the ants of the population have the same characteristics and behaviors. In contrast in this paper, a new type of ant metaheuristic is proposed, namely SMART (for Solution Methods with Ants Running by Types). It relies on the use of different population of ants, where each population has its own personality.

Keywords: ant algorithms, evolutionary procedures, metaheuristics, optimization, population-based methods

Procedia PDF Downloads 329

Authors: C. E. Nugraheni, L. Abednego

Abstract:

This paper is concerned with minimization of mean tardiness and flow time in a real single machine production scheduling problem. Two variants of genetic algorithm as meta-heuristic are combined with hyper-heuristic approach are proposed to solve this problem. These methods are used to solve instances generated with real world data from a company. Encouraging results are reported.

Keywords: hyper-heuristics, evolutionary algorithms, production scheduling, meta-heuristic

Procedia PDF Downloads 352

Authors: Tripatjot S. Panag, J. S. Dhillon

Abstract:

The lifetime of a wireless sensor network can be effectively increased by using scheduling operations. Once the sensors are randomly deployed, the task at hand is to find the largest number of disjoint sets of sensors such that every sensor set provides complete coverage of the target area. At any instant, only one of these disjoint sets is switched on, while all other are switched off. This paper proposes a heuristic search method to find the maximum number of disjoint sets that completely cover the region. A population of randomly initialized members is made to explore the solution space. A set of heuristics has been applied to guide the members to a possible solution in their neighborhood. The heuristics escalate the convergence of the algorithm. The best solution explored by the population is recorded and is continuously updated. The proposed algorithm has been tested for applications which require sensing of multiple target points, referred to as point coverage applications. Results show that the proposed algorithm outclasses the existing algorithms. It always finds the optimum solution, and that too by making fewer number of fitness function evaluations than the existing approaches.

Keywords: coverage, disjoint sets, heuristic, lifetime, scheduling, Wireless sensor networks, WSN

Procedia PDF Downloads 421

Authors: Ehsan Saghehei, Mahdi Eghbali

Abstract:

The maximal covering location problem (MCLP) was originally developed to determine a set of facility locations which would maximize the total customers' demand serviced by the facilities within a predetermined critical service criterion. However, on some problems that differences between the demand nodes are covered or the number of nodes each node is large, the method of solving MCLP may ignore these differences. In this paper, Heuristic solution based on the ranking of demands in each node and the number of nodes covered by each node according to a predetermined critical value is proposed. The output of this method is to maximize total demands of nodes and number of covered nodes, simultaneously. Furthermore, by providing an example, the solution algorithm is described and its results are compared with Greedy and Lagrange algorithms. Also, the results of the algorithm to solve the larger problem sizes that compared with other methods are provided. A summary and future works conclude the paper.

Keywords: heuristic solution, maximal covering location problem, ranking, set covering

Procedia PDF Downloads 542

Authors: Nusrat T. Chowdhury, M. F. Baki, A. Azab

Abstract:

The production planning problem is concerned with specifying the optimal quantities to produce in order to meet the demand for a prespecified planning horizon with the least possible expenditure. Making the right decisions in production planning will affect directly the performance and productivity of a manufacturing firm, which is important for its ability to compete in the market. Therefore, developing and improving solution procedures for production planning problems is very significant. In this paper, we develop a Dantzig-Wolfe decomposition of a multi-item hierarchical production planning problem with capacity constraint and present a column generation approach to solve the problem. The original Mixed Integer Linear Programming model of the problem is decomposed item by item into a master problem and a number of subproblems. The capacity constraint is considered as the linking constraint between the master problem and the subproblems. The subproblems are solved using the dynamic programming approach. We also propose a multi-step iterative capacity allocation heuristic procedure to handle any kind of infeasibility that arises while solving the problem. We compare the computational performance of the developed solution approach against the state-of-the-art heuristic procedure available in the literature. The results show that the proposed heuristic-based decomposition approach improves the solution quality by 20% as compared to the literature.

Keywords: inventory, multi-level capacitated lot-sizing, emission control, setup carryover

Procedia PDF Downloads 103

Authors: Mohsen Ziaee

Abstract:

Almost all existing researches on the flowshop scheduling problems focus on the permutation schedules and there is insufficient study dedicated to the general flowshop scheduling problems in the literature, since the modeling and solving of the general flowshop scheduling problems are more difficult than the permutation ones, especially for the large-size problem instances. This paper considers the general flowshop scheduling problem with the objective function of the makespan (F//Cmax). We first find the optimal solution of the problem by solving a mixed integer linear programming model. An efficient heuristic method is then presented to solve the problem. An ant colony optimization algorithm is also proposed for the problem. In order to evaluate the performance of the methods, computational experiments are designed and performed. Numerical results show that the heuristic algorithm can result in reasonable solutions with low computational effort and even achieve optimal solutions in some cases.

Keywords: scheduling, general flow shop scheduling problem, makespan, heuristic

Procedia PDF Downloads 174

Authors: Mitat Uysal

Abstract:

A new met heuristic optimization algorithm called as Migrating Birds Optimization is used for curve fitting by rational cubic Bezier Curves. This requires solving a complicated multivariate optimization problem. In this study, the solution of this optimization problem is achieved by Migrating Birds Optimization algorithm that is a powerful met heuristic nature-inspired algorithm well appropriate for optimization. The results of this study show that the proposed method performs very well and being able to fit the data points to cubic Bezier Curves with a high degree of accuracy.

Keywords: algorithms, Bezier curves, heuristic optimization, migrating birds optimization

Procedia PDF Downloads 299

Authors: Farzaneh Rajabighamchi, Stan van Hoesel, Christof Defryn

Abstract:

The generalized traveling salesman problem (GTSP) is an extension of the traveling salesman problem (TSP) where the set of nodes is partitioned into clusters, and the salesman must visit exactly one node per cluster. In this research, we apply the definition of the GTSP to an order picker routing problem with multiple locations per product. As such, each product represents a cluster and its corresponding nodes are the locations at which the product can be retrieved. To pick a certain product item from the warehouse, the picker needs to visit one of these locations during its pick tour. As all products are scattered throughout the warehouse, the product clusters not separated geographically. We propose an exact LP model as well as heuristic and meta-heuristic solution algorithms for the order picking problem with multiple product locations.

Keywords: warehouse optimization, order picking problem, generalised travelling salesman problem, heuristic algorithm

Procedia PDF Downloads 77

Authors: Mohammad Pourmohammadi Fallah, Maziar Salahi

Abstract:

In the literature, a mixed-integer linear programming model for the integrated production planning and warehouse layout problem is proposed. To solve the model, the authors proposed a Lagrangian relax-and-fix heuristic that takes a significant amount of time to stop with gaps above 5$\%$ for large-scale instances. Here, we present two heuristic algorithms to solve the problem. In the first one, we use a greedy approach by allocating warehouse locations with less reservation costs and also less transportation costs from the production area to locations and from locations to the output point to items with higher demands. Then a smaller model is solved. In the second heuristic, first, we sort items in descending order according to the fraction of the sum of the demands for that item in the time horizon plus the maximum demand for that item in the time horizon and the sum of all its demands in the time horizon. Then we categorize the sorted items into groups of 3, 4, or 5 and solve a small-scale optimization problem for each group, hoping to improve the solution of the first heuristic. Our preliminary numerical results show the effectiveness of the proposed heuristics.

Keywords: capacitated lot-sizing, warehouse layout, mixed-integer linear programming, heuristics algorithm

Procedia PDF Downloads 152

Authors: Zeyu Zhang, Guisheng Yin, Ziying Zhang, Liguo Zhang

Abstract:

This paper mainly studies the path planning method based on ant colony optimization (ACO), and proposes heuristic integration ant colony optimization (HIACO). This paper not only analyzes and optimizes the principle, but also simulates and analyzes the parameters related to the application of HIACO in path planning. Compared with the original algorithm, the improved algorithm optimizes probability formula, tabu table mechanism and updating mechanism, and introduces more reasonable heuristic factors. The optimized HIACO not only draws on the excellent ideas of the original algorithm, but also solves the problems of premature convergence, convergence to the sub optimal solution and improper exploration to some extent. HIACO can be used to achieve better simulation results and achieve the desired optimization. Combined with the probability formula and update formula, several parameters of HIACO are tested. This paper proves the principle of the HIACO and gives the best parameter range in the research of path planning.

Keywords: ant colony optimization, heuristic integration, path planning, probability formula

Procedia PDF Downloads 212

Authors: Laili Farhana Md Ibharim, Maizatul Hayati Mohamad Yatim

Abstract:

The main purpose of this study is to evaluate the heuristic inspection of children’s authoring tools to develop games. The researcher has selected 15 authoring tools for making games specifically for educational purposes. Nine students from Diploma of Game Design and Development course and four lecturers from the computing department involved in this evaluation. A set of usability heuristic checklist used as a guideline for the students and lecturers to observe and test the authoring tools selected. The study found that there are just a few authoring tools that fulfill most of the heuristic requirement and suitable to apply to children. In this evaluation, only six out of fifteen authoring tools have passed above than five elements in the heuristic inspection checklist. The researcher identified that in order to develop a usable authoring tool developer has to emphasis children acceptance and interaction of the authoring tool. Furthermore, the authoring tool can be a tool to enhance their mental development especially in creativity and skill.

Keywords: authoring tool, children, game making, heuristic

Procedia PDF Downloads 313

Authors: P. Vanichkobchinda

Abstract:

The Logistics Transportation techniques, Open Vehicle Routing (OVR) is an approach toward transportation cost reduction, especially for long distance pickup and delivery nodes. The outstanding characteristic of OVR is that the route starting node and ending node are not necessary the same as in typical vehicle routing problems. This advantage enables the routing to flow continuously and the vehicle does not always return to its home base. This research aims to develop a heuristic for the open vehicle routing problem with pickup and delivery under time window and loading capacity constraints to minimize the total distance. The proposed heuristic is developed based on the Insertion method, which is a simple method and suitable for the rapid calculation that allows insertion of the new additional transportation requirements along the original paths. According to the heuristic analysis, cost comparisons between the proposed heuristic and companies are using method, nearest neighbor method show that the insertion heuristic. Moreover, the proposed heuristic gave superior solutions in all types of test problems. In conclusion, the proposed heuristic can effectively and efficiently solve the open vehicle routing. The research indicates that the improvement of new transport's calculation and the open vehicle routing with "Insertion Heuristic" represent a better outcome with 34.3 percent in average. in cost savings. Moreover, the proposed heuristic gave superior solutions in all types of test problems. In conclusion, the proposed heuristic can effectively and efficiently solve the open vehicle routing.

Keywords: business competitiveness, cost reduction, SMEs, logistics transportation, VRP

Procedia PDF Downloads 655

Authors: S. Adhirai, R. P. Mahapatra, Paramjit Singh

Abstract:

Optimization is an important tool in making decisions and in analysing physical systems. In mathematical terms, an optimization problem is the problem of finding the best solution from among the set of all feasible solutions. The paper discusses the Whale Optimization Algorithm (WOA), and its applications in different fields. The algorithm is tested using MATLAB because of its unique and powerful features. The benchmark functions used in WOA algorithm are grouped as: unimodal (F1-F7), multimodal (F8-F13), and fixed-dimension multimodal (F14-F23). Out of these benchmark functions, we show the experimental results for F7, F11, and F19 for different number of iterations. The search space and objective space for the selected function are drawn, and finally, the best solution as well as the best optimal value of the objective function found by WOA is presented. The algorithmic results demonstrate that the WOA performs better than the state-of-the-art meta-heuristic and conventional algorithms.

Keywords: optimization, optimal value, objective function, optimization problems, meta-heuristic optimization algorithms, Whale Optimization Algorithm, implementation, MATLAB

Procedia PDF Downloads 330

Authors: Yang-Kuei Lin, Yun-Xi Zhang

Abstract:

This research focuses on the bicriteria correlated parallel machine scheduling problem. The two objective functions considered in this problem are to minimize maximum lateness and total weighted completion time. We first present a mixed integer programming (MIP) model that can find the entire efficient frontier for the studied problem. Next, we have proposed a bicriteria heuristic that can find non-dominated solutions for the studied problem. The performance of the proposed bicriteria heuristic is compared with the efficient frontier generated by solving the MIP model. Computational results indicate that the proposed bicriteria heuristic can solve the problem efficiently and find a set of diverse solutions that are uniformly distributed along the efficient frontier.

Keywords: bicriteria, correlated parallel machines, heuristic, scheduling

Procedia PDF Downloads 98

Authors: Khaled Moh. Alhamad

Abstract:

This paper describes a tabu search heuristic for a ship routing and scheduling problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous vessels. Constraints relate to delivery time windows imposed by customers, the time horizon by which all deliveries must be made and vessel capacities. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the tabu search such as tenure and neighbourhood size.

Keywords: heuristic, scheduling, tabu search, transportation

Procedia PDF Downloads 475

Authors: Ghada Moussa, Mamoud Owais

Abstract:

Transit Route Network Design Problem (TrNDP) is the most important component in Transit planning, in which the overall cost of the public transportation system highly depends on it. The main purpose of this study is to develop a novel solution methodology for the TrNDP, which goes beyond pervious traditional sophisticated approaches. The novelty of the solution methodology, adopted in this paper, stands on the deterministic operators which are tackled to construct bus routes. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can be solved exactly with their standard solvers. The solution methodology has been tested through Mandl’s benchmark network problem. The test results showed that the methodology developed in this research is able to improve the given network solution in terms of number of constructed routes, direct transit service coverage, transfer directness and solution reliability. Although the set of routes resulted from the methodology would stand alone as a final efficient solution for TrNDP, it could be used as an initial solution for meta-heuristic procedures to approach global optimal. Based on the presented methodology, a more robust network optimization tool would be produced for public transportation planning purposes.

Keywords: integer programming, transit route design, transportation, urban planning

Procedia PDF Downloads 233

Authors: Guilherme Baldo Carlos

Abstract:

The flexible job-shop scheduling problem (FJSP) is an NP-hard combinatorial optimization problem, which can be applied to model several applications in a wide array of industries. This problem will have its importance increase due to the shift in the production mode that modern society is going through. The demands are increasing and for products personalized and customized. This work aims to apply a meta-heuristic called a genetic algorithm (GA) to solve this problem. A GA is a meta-heuristic inspired by the natural selection of Charles Darwin; it produces a population of individuals (solutions) and selects, mutates, and mates the individuals through generations in order to find a good solution for the problem. The results found indicate that the GA is suitable for FJSP solving.

Keywords: genetic algorithm, evolutionary algorithm, scheduling, flexible job-shop scheduling

Procedia PDF Downloads 115

Authors: Sami Baraketi, Jean Marie Garcia, Olivier Brun

Abstract:

Wavelength Division Multiplexing (WDM) is the dominant transport technology used in numerous high capacity backbone networks, based on optical infrastructures. Given the importance of costs (CapEx and OpEx) associated to these networks, resource management is becoming increasingly important, especially how the optical circuits, called “lightpaths”, are routed throughout the network. This requires the use of efficient algorithms which provide routing strategies with the lowest cost. We focus on the lightpath routing and wavelength assignment problem, known as the RWA problem, while optimizing wavelength fragmentation over the network. Wavelength fragmentation poses a serious challenge for network operators since it leads to the misuse of the wavelength spectrum, and then to the refusal of new lightpath requests. In this paper, we first establish a new Integer Linear Program (ILP) for the problem based on a node-link formulation. This formulation is based on a multilayer approach where the original network is decomposed into several network layers, each corresponding to a wavelength. Furthermore, we propose an efficient heuristic for the problem based on a greedy algorithm followed by a post-treatment procedure. The obtained results show that the optimal solution is often reached. We also compare our results with those of other RWA heuristic methods.

Keywords: WDM, lightpath, RWA, wavelength fragmentation, optimization, linear programming, heuristic

Procedia PDF Downloads 496

Authors: Christian Meinecke, Bernd Scholz-Reiter

Abstract:

The integrated problem of production and distribution scheduling is relevant in many industrial applications. Thus, many heuristics to solve this integrated problem have been developed in the last decade. Most of these heuristics use a sequential working principal or a single decomposition and integration approach to separate and solve sub-problems. A heuristic using a multi-step decomposition and integration approach is presented in this paper and evaluated in a case study. The result show significant improved results compared with sequential scheduling heuristics.

Keywords: production and outbound distribution, integrated planning, heuristic, decomposition, integration

Procedia PDF Downloads 390

Authors: Sheila Shamuganathan, Mageswary Karpudewan

Abstract:

This study investigated the effectiveness of green chemistry integrated with Science Writing Heuristic (SWH) in enhancing matriculation students’ responsible environmental behaviour. For this purpose 207 matriculation students were randomly assigned into experimental (N=118) and control (N=89) group. For the experimental group the chemistry concepts were taught using the instructional approach of green chemistry integrated with Science Writing Heuristic (SWH) while for the control group the same content was taught using green chemistry. The data was analysed using ANCOVA and findings obtained from the quantitative analysis reveals that there is significant changes in responsible environmental behaviour (F 1,204) = 32.13 (ηp² = 0.14) which favours the experimental group. The responses of the qualitative data obtained from an interview with the experimental group also further strengthen and indicated a significant improvement in responsible environmental behaviour. The outcome of the study suggests that using green chemistry integrated with Science Writing Heuristic (SWH) could be an alternative approach to improve students’ responsible environmental behaviour towards the environment.

Keywords: science writing heuristic, green chemistry, pro environmental behaviour, laboratory

Procedia PDF Downloads 280

Authors: Zaid Jamal Saeed Almahmoud

Abstract:

Smart grid is emerging as the future power grid, with smart techniques to optimize power consumption and electricity generation. Minimizing peak power consumption under a fixed delay requirement is a significant problem in the smart grid.For this problem, all appliances must be scheduled within a given finite time duration. We consider the problem of minimizing the peak demand under appliances constraints by scheduling power jobs with uniform release dates and deadlines. As the problem is known to be NP-hard, we analyze the performance of a version of the natural greedy heuristic for solving this problem. Our theoretical analysis and experimental results show that the proposed heuristic outperforms existing methods by providing a better approximation to the optimal solution.

Keywords: peak demand scheduling, approximation algorithms, smart grid, heuristics

Procedia PDF Downloads 62

Authors: Mehdi Seifbarghy, Zahra Nasiri

Abstract:

Competitive location problem deals with locating new facilities to provide a service (or goods) to the customers of a given geographical area where other facilities (competitors) offering the same service are already present. The new facilities will have to compete with the existing facilities for capturing the market share. This paper proposes a new model to maximize the market share in which customers choose the facilities based on traveling time, waiting time and attractiveness. The attractiveness of a facility is considered as a parameter in the model. A heuristic is proposed to solve the problem.

Keywords: competitive location, market share, facility attractiveness, heuristic

Procedia PDF Downloads 490

Authors: K. Y. Tseng, C. Y. Wu

Abstract:

This paper employs a heuristic algorithm to solve engineering problems including truss structure optimization and optimal chiller loading (OCL) problems. Two different type algorithms, real-valued differential evolution (DE) and modified binary differential evolution (MBDE), are successfully integrated and then can obtain better performance in solving engineering problems. In order to demonstrate the performance of the proposed algorithm, this study adopts each one testing case of truss structure optimization and OCL problems to compare the results of other heuristic optimization methods. The result indicates that the proposed algorithm can obtain similar or better solution in comparing with previous studies.

Keywords: differential evolution, Truss structure optimization, optimal chiller loading, modified binary differential evolution

Procedia PDF Downloads 131

Authors: Saeed Poormoaied, Zumbul Atan

Abstract:

Emergency shipments provide a powerful mechanism to alleviate the risk of imminent stock-outs and can result in substantial benefits in an inventory system. Customer satisfaction and high service level are immediate consequences of utilizing emergency shipments. In this paper, we consider a single-echelon periodic review inventory system consisting of a single local warehouse, being replenished from a central warehouse with ample capacity in an infinite horizon setting. Since the structure of the optimal policy appears to be complicated, we analyze this problem under an order-up-to-S inventory control policy framework, the (S, T) policy, with the emergency shipment consideration. In each period of the periodic review policy, there is a single opportunity at any point of time for the emergency shipment so that in case of stock-outs, an emergency shipment is requested. The goal is to determine the timing and amount of the emergency shipment during a period (emergency shipment policy) as well as the base stock periodic review policy parameters (replenishment policy). We show that how taking advantage of having an emergency shipment during periods improves the performance of the classical (S, T) policy, especially when fixed and unit emergency shipment costs are small. Investigating the structure of the objective function, we develop an exact algorithm for finding the optimal solution. We also provide a heuristic and an approximation algorithm for the periodic review inventory system problem. The experimental analyses indicate that the heuristic algorithm is computationally more efficient than the approximation algorithm, but in terms of the solution efficiency, the approximation algorithm performs very well. We achieve up to 13% cost savings in the (S, T) policy if we apply the proposed emergency shipment policy. Moreover, our computational results reveal that the approximated solution is often within 0.21% of the globally optimal solution.

Keywords: emergency shipment, inventory, periodic review policy, approximation algorithm.

Procedia PDF Downloads 110

Authors: Regita P. Permata, Ulfa S. Nuraini

Abstract:

Traveling Salesman Problem (TSP) is the most studied problem in combinatorial optimization. In simple language, TSP can be described as a problem of finding a minimum distance tour to a city, starting and ending in the same city, and exactly visiting another city. In product distribution, companies often get problems in determining the minimum distance that affects the time allocation. In this research, we aim to apply TSP heuristic methods to simulate nodes as city coordinates in product distribution. The heuristics used are sub tour reversal, nearest neighbor, farthest insertion, cheapest insertion, nearest insertion, and arbitrary insertion. We have done simulation nodes using Euclidean distances to compare the number of cities and processing time, thus we get optimum heuristic method. The results show that the optimum heuristic methods are farthest insertion and nearest insertion. These two methods can be recommended to solve product distribution problems in certain companies.

Keywords: Euclidean, heuristics, simulation, TSP

Procedia PDF Downloads 99

Authors: Gianpaolo Ghiani, Emanuela Guerriero, Emanuele Manni, Alessandro Romano

Abstract:

In this article, we deal with a variant of the classical course timetabling problem that has a practical application in many areas of education. In particular, in this paper we are interested in high schools remedial courses. The purpose of such courses is to provide under-prepared students with the skills necessary to succeed in their studies. In particular, a student might be under prepared in an entire course, or only in a part of it. The limited availability of funds, as well as the limited amount of time and teachers at disposal, often requires schools to choose which courses and/or which teaching units to activate. Thus, schools need to model the training offer and the related timetabling, with the goal of ensuring the highest possible teaching quality, by meeting the above-mentioned financial, time and resources constraints. Moreover, there are some prerequisites between the teaching units that must be satisfied. We first present a Mixed-Integer Programming (MIP) model to solve this problem to optimality. However, the presence of many peculiar constraints contributes inevitably in increasing the complexity of the mathematical model. Thus, solving it through a general purpose solver may be performed for small instances only, while solving real-life-sized instances of such model requires specific techniques or heuristic approaches. For this purpose, we also propose a heuristic approach, in which we make use of a fast constructive procedure to obtain a feasible solution. To assess our exact and heuristic approaches we perform extensive computational results on both real-life instances (obtained from a high school in Lecce, Italy) and randomly generated instances. Our tests show that the MIP model is never solved to optimality, with an average optimality gap of 57%. On the other hand, the heuristic algorithm is much faster (in about the 50% of the considered instances it converges in approximately half of the time limit) and in many cases allows achieving an improvement on the objective function value obtained by the MIP model. Such an improvement ranges between 18% and 66%.

Keywords: heuristic, MIP model, remedial course, school, timetabling

Procedia PDF Downloads 574

Authors: Eldho Paul, Brijesh Paul

Abstract:

This work proposes an auction mechanism based solution methodology for the optimum scheduling of trucks in a cross-docking centre. The cross-docking centre is an important element of lean supply chain. It reduces the amount of storage and transportation costs in the distribution system compared to an ordinary warehouse. Better scheduling of trucks in a cross-docking center is the best way to reduce storage and transportation costs. Auction mechanism is commonly used for allocation of limited resources in different real-life applications. Here, we try to schedule inbound trucks by integrating auction mechanism with the functioning of a cross-docking centre. A mathematical model is developed for the optimal scheduling of inbound trucks based on the auction methodology. The determination of exact solution for problems involving large number of trucks was found to be computationally difficult, and hence a genetic algorithm based heuristic methodology is proposed in this work. A comparative study of exact and heuristic solutions is done using five classes of data sets. It is observed from the study that the auction-based mechanism is capable of providing good solutions to scheduling problem in cross-docking centres.

Keywords: auction mechanism, cross-docking centre, genetic algorithm, scheduling of trucks

Procedia PDF Downloads 379

Authors: Mahmoud M. Othman, Y. G. Hegazy, A. Y. Abdelaziz

Abstract:

This paper proposes a novel heuristic algorithm that aims to determine the best size and location of distributed generators in unbalanced distribution networks. The proposed heuristic algorithm can deal with the planning cases where power loss is to be optimized without violating the system practical constraints. The distributed generation units in the proposed algorithm is modeled as voltage controlled node with the flexibility to be converted to constant power factor node in case of reactive power limit violation. The proposed algorithm is implemented in MATLAB and tested on the IEEE 37 -node feeder. The results obtained show the effectiveness of the proposed algorithm.

Keywords: distributed generation, heuristic approach, optimization, planning

Procedia PDF Downloads 488