Search results for: permutation flow shop problem

Authors: Watchara Songserm, Teeradej Wuttipornpun

Abstract:

This paper presents a genetic algorithm based permutation and non-permutation scheduling heuristics (GAPNP) to solve a multi-stage finite capacity material requirement planning (FCMRP) problem in automotive assembly flow shop with unrelated parallel machines. In the algorithm, the sequences of orders are iteratively improved by the GA characteristics, whereas the required operations are scheduled based on the presented permutation and non-permutation heuristics. Finally, a linear programming is applied to minimize the total cost. The presented GAPNP algorithm is evaluated by using real datasets from automotive companies. The required parameters for GAPNP are intently tuned to obtain a common parameter setting for all case studies. The results show that GAPNP significantly outperforms the benchmark algorithm about 30% on average.

Keywords: capacitated MRP, genetic algorithm, linear programming, automotive industries, flow shop, application in industry

Procedia PDF Downloads 458

Authors: G. M. Komaki, S. Mobin, E. Teymourian, S. Sheikh

Abstract:

This paper addresses minimizing the makespan of the distributed permutation flow shop scheduling problem. In this problem, there are several parallel identical factories or flowshops each with series of similar machines. Each job should be allocated to one of the factories and all of the operations of the jobs should be performed in the allocated factory. This problem has recently gained attention and due to NP-Hard nature of the problem, metaheuristic algorithms have been proposed to tackle it. Majority of the proposed algorithms require large computational time which is the main drawback. In this study, a general variable neighborhood search algorithm (GVNS) is proposed where several time-saving schemes have been incorporated into it. Also, the GVNS uses the sophisticated method to change the shaking procedure or perturbation depending on the progress of the incumbent solution to prevent stagnation of the search. The performance of the proposed algorithm is compared to the state-of-the-art algorithms based on standard benchmark instances.

Keywords: distributed permutation flow shop, scheduling, makespan, general variable neighborhood search algorithm

Procedia PDF Downloads 327

Authors: Ebrahim Asadi-Gangraj

Abstract:

Hybrid flow shop scheduling problem (HFS) contains sequencing in a flow shop where, at any stage, there exist one or more related or unrelated parallel machines. This production system is a common manufacturing environment in many real industries, such as the steel manufacturing, ceramic tile manufacturing, and car assembly industries. In this research, a mixed integer linear programming (MILP) model is presented for the hybrid flow shop scheduling problem, in which, the objective consists of minimizing the maximum completion time (makespan). For this purpose, a Benders Decomposition (BD) method is developed to solve the research problem. The proposed approach is tested on some test problems, small to moderate scale. The experimental results show that the Benders decomposition approach can solve the hybrid flow shop scheduling problem in a reasonable time, especially for small and moderate-size test problems.

Keywords: hybrid flow shop, mixed integer linear programming, Benders decomposition, makespan

Procedia PDF Downloads 145

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: J. Kaabi, Y. Harrath

Abstract:

This paper studied the flow shop scheduling problem under machine availability constraints. The machines are subject to flexible preventive maintenance activities. The nonresumable scenario for the jobs was considered. That is, when a job is interrupted by an unavailability period of a machine it should be restarted from the beginning. The objective is to minimize the total tardiness time for the jobs and the advance/tardiness for the maintenance activities. To solve the problem, a genetic algorithm was developed and successfully tested and validated on many problem instances. The computational results showed that the new genetic algorithm outperforms another earlier proposed algorithm.

Keywords: flow shop scheduling, genetic algorithm, maintenance, priority rules

Procedia PDF Downloads 442

Authors: Samia Kouki

Abstract:

Solving NP-hard combinatorial optimization problems by exact search methods, such as Branch-and-Bound, may degenerate to complete enumeration. For that reason, exact approaches limit us to solve only small or moderate size problem instances, due to the exponential increase in CPU time when problem size increases. One of the most promising ways to reduce significantly the computational burden of sequential versions of Branch-and-Bound is to design parallel versions of these algorithms which employ several processors. This paper describes a parallel Branch-and-Bound algorithm called GALB for solving the classical permutation flowshop scheduling problem as well as its implementation on a Grid computing infrastructure. The experimental study of our distributed parallel algorithm gives promising results and shows clearly the benefit of the parallel paradigm to solve large-scale instances in moderate CPU time.

Keywords: grid computing, permutation flow shop problem, branch and bound, load balancing

Procedia PDF Downloads 248

Authors: Joselito Medina Marin, Norberto Hernández Romero, Juan Carlos Seck Tuoh Mora, Erick S. Martinez Gomez

Abstract:

The Flow Shop Scheduling Problem (FSSP) is a typical problem that is faced by production planning managers in Flexible Manufacturing Systems (FMS). This problem consists in finding the optimal scheduling to carry out a set of jobs, which are processed in a set of machines or shared resources. Moreover, all the jobs are processed in the same machine sequence. As in all the scheduling problems, the makespan can be obtained by drawing the Gantt chart according to the operations order, among other alternatives. On this way, an FMS presenting the FSSP can be modeled by Petri nets (PNs), which are a powerful tool that has been used to model and analyze discrete event systems. Then, the makespan can be obtained by simulating the PN through the token game animation and incidence matrix. In this work, we present an adaptive PN to obtain the makespan of FSSP by applying PN analytical tools.

Keywords: flow-shop scheduling problem, makespan, Petri nets, state equation

Procedia PDF Downloads 263

Authors: Saeedeh Ahmadi Basir, Mohammad Mahdavi Mazdeh, Mohammad Namakshenas

Abstract:

Manufacturers often dispatch jobs in batches to reduce delivery costs. However, sending several jobs in batches can have a negative effect on other scheduling-related objective functions such as minimizing the number of tardy jobs which is often used to rate managers’ performance in many manufacturing environments. This paper aims to minimize the number of weighted tardy jobs and the sum of delivery costs of a two-stage assembly flow-shop problem in a batch delivery system. We present a mixed-integer linear programming (MILP) model to solve the problem. As this is an MILP model, the commercial solver (the CPLEX solver) is not guaranteed to find the optimal solution for large-size problems at a reasonable amount of time. We present several numerical examples to confirm the accuracy of the model.

Keywords: scheduling, two-stage assembly flow-shop, tardy jobs, batched delivery system

Procedia PDF Downloads 428

Authors: Rui Wu

Abstract:

In the volatile modern manufacturing environment, new orders randomly occur at any time, while the pre-emptive methods are infeasible. This leads to a real-time scheduling method that can produce a reasonably good schedule quickly. The dynamic Flexible Job Shop problem is an NP-hard scheduling problem that hybrid the dynamic Job Shop problem with the Parallel Machine problem. A Flexible Job Shop contains different work centres. Each work centre contains parallel machines that can process certain operations. Many algorithms, such as genetic algorithms or simulated annealing, have been proposed to solve the static Flexible Job Shop problems. However, the time efficiency of these methods is low, and these methods are not feasible in a dynamic scheduling problem. Therefore, a dynamic rule selection scheduling system based on the reinforcement learning method is proposed in this research, in which the dynamic Flexible Job Shop problem is divided into several parallel machine problems to decrease the complexity of the dynamic Flexible Job Shop problem. Firstly, the features of jobs, machines, work centres, and flexible job shops are selected to describe the status of the dynamic Flexible Job Shop problem at each decision point in each work centre. Secondly, a framework of reinforcement learning algorithm using a double-layer deep Q-learning network is applied to select proper composite dispatching rules based on the status of each work centre. Then, based on the selected composite dispatching rule, an available operation is selected from the waiting buffer and assigned to an available machine in each work centre. Finally, the proposed algorithm will be compared with well-known dispatching rules on objectives of mean tardiness, mean flow time, mean waiting time, or mean percentage of waiting time in the real-time Flexible Job Shop problem. The result of the simulations proved that the proposed framework has reasonable performance and time efficiency.

Keywords: dynamic scheduling problem, flexible job shop, dispatching rules, deep reinforcement learning

Procedia PDF Downloads 71

Authors: Hernández Eva Selene, Reyna Mary Carmen, Rivera Héctor, Barragán Irving

Abstract:

We propose an approach that jointly addresses the layout of a facility and the scheduling of a sequence of jobs. In real production, these two problems are interrelated. However, they are treated separately in the literature. Our approach is an extension of the job shop problem with transportation delay, where the location of the machines is selected among possible sites. The model minimizes the makespan, using the short processing times rule with two algorithms; the first one considers all the permutations for the location of machines, and the second only a heuristic to select some specific permutations that reduces computational time. Some instances are proved and compared with literature.

Keywords: layout problem, job shop scheduling problem, concurrent scheduling and layout problem, metaheuristic

Procedia PDF Downloads 579

Authors: Amin Saeidi

Abstract:

Using a representation-theoretic approach and considering G to be a finite primitive permutation group of degree n, our aim is to determine linear codes of length n that admit G as a permutation automorphism group. We can show that in some cases, every binary linear code admitting G as a permutation automorphism group is a submodule of a permutation module defined by a primitive action of G. As an illustration of the method, we consider the sporadic simple group M₁₁ and the unitary group U(3,3). We also construct some point- and block-primitive 1-designs from the supports of some codewords of the codes in the discussion.

Keywords: linear code, permutation representation, support design, simple group

Procedia PDF Downloads 45

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: Midhun Paul, T. Radha Ramanan

Abstract:

The objective of this work is to present a state-of-the-art literature review highlighting the challenges in the research of the scheduling of assembly job shop problem and providing an insight on how the future directions of the research would be. The number of work has been substantial that it requires a review to enable one to understand the origin of the research and how it is getting evolved. This review paper presents a comprehensive review of the literature dealing with various studies carried on assembly job shop scheduling. The review details the evolution of the AJS from the perspective of other scheduling problems and also presents a classification scheme. The work also identifies the potential directions for future research, which we believe to be worthwhile considering.

Keywords: assembly job shop, future directions, manufacturing, scheduling

Procedia PDF Downloads 382

Authors: M. Ndeley

Abstract:

Now our days, Almost all manufacturing facilities need to use production planning and scheduling systems to increase productivity and to reduce production costs. Real-life production operations are subject to a large number of unexpected disruptions that may invalidate the original schedules. In these cases, rescheduling is essential to minimize the impact on the performance of the system. In this work we consider flow shop layouts that have seldom been studied in the rescheduling literature. We generate and employ three types of disruption that interrupt the original schedules simultaneously. We develop rescheduling algorithms to finally accomplish the twofold objective of establishing a standard framework on the one hand; and proposing rescheduling methods that seek a good trade-off between schedule quality and stability on the other.

Keywords: flow shop scheduling, uncertainty, rescheduling, stability

Procedia PDF Downloads 409

Authors: Majid Abdolrazzagh-Nezhad, Salwani Abdullah

Abstract:

The job-shop scheduling problem (JSSP) is an important decision facing those involved in the fields of industry, economics and management. This problem is a class of combinational optimization problem known as the NP-hard problem. JSSPs deal with a set of machines and a set of jobs with various predetermined routes through the machines, where the objective is to assemble a schedule of jobs that minimizes certain criteria such as makespan, maximum lateness, and total weighted tardiness. Over the past several decades, interest in meta-heuristic approaches to address JSSPs has increased due to the ability of these approaches to generate solutions which are better than those generated from heuristics alone. This article provides the classification, constraints and objective functions imposed on JSSPs that are available in the literature.

Keywords: job-shop scheduling, classification, constraints, objective functions

Procedia PDF Downloads 410

Authors: Watcharapan Sukkerd, Teeradej Wuttipornpun

Abstract:

This paper aims to present non-population search algorithms called tabu search (TS), simulated annealing (SA) and variable neighborhood search (VNS) to minimize the total cost of capacitated MRP problem in multi-stage assembly flow shop with two alternative machines. There are three main steps for the algorithm. Firstly, an initial sequence of orders is constructed by a simple due date-based dispatching rule. Secondly, the sequence of orders is repeatedly improved to reduce the total cost by applying TS, SA and VNS separately. Finally, the total cost is further reduced by optimizing the start time of each operation using the linear programming (LP) model. Parameters of the algorithm are tuned by using real data from automotive companies. The result shows that VNS significantly outperforms TS, SA and the existing algorithm.

Keywords: capacitated MRP, tabu search, simulated annealing, variable neighborhood search, linear programming, assembly flow shop, application in industry

Procedia PDF Downloads 207

Authors: Aydin Teymourifar, Gurkan Ozturk

Abstract:

In this paper, a distributed hybrid algorithm is proposed for solving the job shop scheduling problem. The suggested method executes different artificial neural networks, heuristics and meta-heuristics simultaneously on more than one machine. The neural networks are used to control the constraints of the problem while the meta-heuristics search the global space and the heuristics are used to prevent the premature convergence. To attain an efficient distributed intelligent method for solving big and distributed job shop scheduling problems, Apache Spark and Hadoop frameworks are used. In the algorithm implementation and design steps, new approaches are applied. Comparison between the proposed algorithm and other efficient algorithms from the literature shows its efficiency, which is able to solve large size problems in short time.

Keywords: distributed algorithms, Apache Spark, Hadoop, job shop scheduling, neural network

Procedia PDF Downloads 351

Authors: Tarek Aboueldahab, Hanan Farag

Abstract:

Parallel Job Shop Scheduling Problem (JSP) is a multi-objective and multi constrains NP- optimization problem. Traditional Artificial Intelligence techniques have been widely used; however, they could be trapped into the local minimum without reaching the optimum solution, so we propose a hybrid Artificial Intelligence model (AI) with Discrete Breeding Swarm (DBS) added to traditional Artificial Intelligence to avoid this trapping. This model is applied in the cost minimization of the Car Sequencing and Operator Allocation (CSOA) problem. The practical experiment shows that our model outperforms other techniques in cost minimization.

Keywords: parallel job shop scheduling problem, artificial intelligence, discrete breeding swarm, car sequencing and operator allocation, cost minimization

Procedia PDF Downloads 144

Authors: Christian Böning, Henrik Prinzhorn, Eric C. Hund, Malte Stonis

Abstract:

In this article, the flexible job-shop scheduling problem is extended by consideration of energy costs which arise owing to the power peak, and further decision variables such as work in process and throughput time are incorporated into the objective function. This enables a production plan to be simultaneously optimized in respect of the real arising energy and logistics costs. The energy-costs-aware flexible job-shop scheduling problem (EFJSP) which arises is described mathematically, and a memetic algorithm (MA) is presented as a solution. In the MA, the evolutionary process is supplemented with a local search. Furthermore, repair procedures are used in order to rectify any infeasible solutions that have arisen in the evolutionary process. The potential for lowering the real arising costs of a production plan through consideration of energy consumption levels is highlighted.

Keywords: energy costs, flexible job-shop scheduling, memetic algorithm, power peak

Procedia PDF Downloads 306

Authors: Marcel Heimar Ribeiro Utiyama, Fernanda Caveiro Correia, Dario Henrique Alliprandini

Abstract:

The importance of the correct allocation of improvement programs is of growing interest in recent years. Due to their limited resources, companies must ensure that their financial resources are directed to the correct workstations in order to be the most effective and survive facing the strong competition. However, to our best knowledge, the literature about allocation of improvement programs does not analyze in depth this problem when the flow shop process has two capacity constrained resources. This is a research gap which is deeply studied in this work. The purpose of this work is to identify the best strategy to allocate improvement programs in a flow shop with two capacity constrained resources. Data were collected from a flow shop process with seven workstations in an industrial control and automation company, which process 13.690 units on average per month. The data were used to conduct a simulation with the System Dynamics-Factory Physics model. The main variables considered, due to their importance on lead time reduction, were the mean time between failures and the mean time to repair. The lead time reduction was the output measure of the simulations. Ten different strategies were created: (i) focused time to repair improvement, (ii) focused time between failures improvement, (iii) distributed time to repair improvement, (iv) distributed time between failures improvement, (v) focused time to repair and time between failures improvement, (vi) distributed time to repair and between failures improvement, (vii) hybrid time to repair improvement, (viii) hybrid time between failures improvements, (ix) time to repair improvement strategy towards the two capacity constrained resources, (x) time between failures improvement strategy towards the two capacity constrained resources. The ten strategies tested are variations of the three main strategies for improvement programs named focused, distributed and hybrid. Several comparisons among the effect of the ten strategies in lead time reduction were performed. The results indicated that for the flow shop analyzed, the focused strategies delivered the best results. When it is not possible to perform a large investment on the capacity constrained resources, companies should use hybrid approaches. An important contribution to the academy is the hybrid approach, which proposes a new way to direct the efforts of improvements. In addition, the study in a flow shop with two strong capacity constrained resources (more than 95% of utilization) is an important contribution to the literature. Another important contribution is the problem of allocation with two CCRs and the possibility of having floating capacity constrained resources. The results provided the best improvement strategies considering the different strategies of allocation of improvement programs and different positions of the capacity constrained resources. Finally, it is possible to state that both strategies, hybrid time to repair improvement and hybrid time between failures improvement, delivered best results compared to the respective distributed strategies. The main limitations of this study are mainly regarding the flow shop analyzed. Future work can further investigate different flow shop configurations like a varying number of workstations, different number of products or even different positions of the two capacity constrained resources.

Keywords: allocation of improvement programs, capacity constrained resource, hybrid strategy, lead time, mean time to repair, mean time between failures

Procedia PDF Downloads 87

Authors: Mohsen Ziaee

Abstract:

In this paper, a mixed integer linear programming (MILP) model is presented to solve the flexible job shop scheduling problem (FJSP). This problem is one of the hardest combinatorial problems. The objective considered is the minimization of the makespan. The computational results of the proposed MILP model were compared with those of the best known mathematical model in the literature in terms of the computational time. The results show that our model has better performance with respect to all the considered performance measures including relative percentage deviation (RPD) value, number of constraints, and total number of variables. By this improved mathematical model, larger FJS problems can be optimally solved in reasonable time, and therefore, the model would be a better tool for the performance evaluation of the approximation algorithms developed for the problem.

Keywords: scheduling, flexible job shop, makespan, mixed integer linear programming

Procedia PDF Downloads 150

Authors: Viraj Tyagi, Ajai Jain, P. K. Jain, Aarushi Jain

Abstract:

This paper presents a genetic algorithm based loading methodology for a capacity constrained job-shop with the consideration of alternative process plans for each part to be produced. Performance analysis of the proposed methodology is carried out for two case studies by considering two different manufacturing scenarios. Results obtained indicate that the methodology is quite effective in improving the shop load balance, and hence, it can be included in the frameworks of manufacturing planning systems of job-shop oriented industries.

Keywords: manufacturing planning, loading, genetic algorithm, job shop

Procedia PDF Downloads 265

Authors: J. Ikome, M. Ndeley

Abstract:

When a machine breakdown forces a Modified Flow Shop (MFS) out of the prescribed state, the proposed strategy reschedules part of the initial schedule to match up with the preschedule at some point. The objective is to create a new schedule that is consistent with the other production planning decisions like material flow, tooling and purchasing by utilizing the time critical decision making concept. We propose a new rescheduling strategy and a match-up point determination procedure through a feedback mechanism to increase both the schedule quality and stability. The proposed approach is compared with alternative reactive scheduling methods under different experimental settings.

Keywords: advanced critical task methods modified flow shop (MFS), Manufacturing, experiment, determination

Procedia PDF Downloads 381

Authors: Sanjay Kumar Parjapati, Ajai Jain

Abstract:

This paper presents optimization of makespan for ‘n’ jobs and ‘m’ machines flexible job shop scheduling problem with sequence dependent setup time using genetic algorithm (GA) approach. A restart scheme has also been applied to prevent the premature convergence. Two case studies are taken into consideration. Results are obtained by considering crossover probability (pc = 0.85) and mutation probability (pm = 0.15). Five simulation runs for each case study are taken and minimum value among them is taken as optimal makespan. Results indicate that optimal makespan can be achieved with more than one sequence of jobs in a production order.

Keywords: flexible job shop, genetic algorithm, makespan, sequence dependent setup times

Procedia PDF Downloads 299

Authors: Abdelhadi Adel, Kadri Ouahab

Abstract:

This paper proposes a hybrid algorithm for the integration of systematic preventive maintenance policies in hybrid flow shop scheduling to minimize makespan. We have implemented a problem-solving approach for optimizing the processing time, methods based on metaheuristics. The proposed approach is inspired by the behavior of the human body. This hybridization is between a multi-agent system and inspirations of the human body, especially genetics. The effectiveness of our approach has been demonstrated repeatedly in this paper. To solve such a complex problem, we proposed an approach which we have used advanced operators such as uniform crossover set and single point mutation. The proposed approach is applied to three preventive maintenance policies. These policies are intended to maximize the availability or to maintain a minimum level of reliability during the production chain. The results show that our algorithm outperforms existing algorithms. We assumed that the machines might be unavailable periodically during the production scheduling.

Keywords: multi-agent systems, emergence, genetic algorithm, makespan, systematic maintenance, scheduling, hybrid flow shop scheduling

Procedia PDF Downloads 305

Authors: Majid Khalili, Hamed Tayebi

Abstract:

This paper considers a stochastic flexible job-shop scheduling (SFJSS) problem in the presence of production disruptions, and reactive scheduling is implemented in order to find the optimal solution under uncertainty. In this problem, there are two main disruptions including machine failure which influences operation time, and modification or cancellation of the order delivery date during production. In order to decrease the negative effects of these difficulties, two derived strategies from reactive scheduling are used; the first one is relevant to being able to allocate multiple machine to each job, and the other one is related to being able to select the best alternative process from other job while some disruptions would be created in the processes of a job. For this purpose, a Mixed Integer Linear Programming model is proposed.

Keywords: flexible job-shop scheduling, reactive scheduling, stochastic environment, mixed integer linear programming

Procedia PDF Downloads 329

Authors: Aydin Teymourifar, Gurkan Ozturk, Ozan Bahadir

Abstract:

NSGA-II is one of the most well-known and most widely used evolutionary algorithms. In addition to its new versions, such as NSGA-III, there are several modified types of this algorithm in the literature. In this paper, a hybrid NSGA-II algorithm has been suggested for solving the multi-objective flexible job shop scheduling problem. For a better search, new neighborhood-based crossover and mutation operators are defined. To create new generations, the neighbors of the selected individuals by the tournament selection are constructed. Also, at the end of each iteration, before sorting, neighbors of a certain number of good solutions are derived, except for solutions protected by elitism. The neighbors are generated using a constraint-based neural network that uses various constructs. The non-dominated sorting and crowding distance operators are same as the classic NSGA-II. A comparison based on some multi-objective benchmarks from the literature shows the efficiency of the algorithm.

Keywords: flexible job shop scheduling problem, multi-objective optimization, NSGA-II algorithm, neighborhood structures

Procedia PDF Downloads 190

Authors: Daniel Panario, Daniel Santana de Freitas, Brett Stevens

Abstract:

Almost Perfect Nonlinear (APN) permutations with optimal resistance against differential cryptanalysis can be found in several domains. The permutation used in the standard for symmetric cryptography (the AES), for example, is based on a special kind of inversion in GF(28). Although very close to APN (2-uniform), this permutation still contains one number 4 in its differential spectrum, which means that, rigorously, it must be classified as 4-uniform. This fact motivates the search for fully APN permutations in other domains of definition. The extremely high complexity associated to this kind of problem precludes an exhaustive search for an APN permutation with 256 elements to be performed without the support of a suitable mathematical structure. On the other hand, in principle, there is nothing to indicate which mathematically structured domains can effectively help the search, and it is necessary to test several domains. In this work, the search for APN permutations in rings ℤ2×ℤ2k is investigated. After a full, exhaustive search with k=2 and k=3, all possible APN permutations in those rings were recorded, together with their differential profiles. Some very promising heuristics in these cases were collected so that, when used as a basis to prune backtracking for the same search in ℤ2×ℤ8 (search space with size 16! ≅244), just a few tenths of a second were enough to produce an APN permutation in a single CPU. Those heuristics were empirically extrapolated so that they could be applied to a backtracking search for APNs over ℤ2×ℤ16 (search space with size 32! ≅2117). The best permutations found in this search were further refined through Simulated Annealing, with a definition of neighbors suitable to this domain. The best result produced with this scheme was a 3-uniform permutation over ℤ2×ℤ16 with only 24 values equal to 3 in the differential spectrum (all the other 968 values were less than or equal 2, as it should be the case for an APN permutation). Although far from being fully APN, this result is technically better than a 4-uniform permutation and demanded only a few seconds in a single CPU. This is a strong indication that the use of mathematically structured domains, like the rings described in this work, together with heuristics based on smaller cases, can lead to dramatic cuts in the computational resources involved in the complexity of the search for APN permutations in extremely large domains.

Keywords: APN permutations, heuristic searches, symmetric cryptography, S-box design

Procedia PDF Downloads 125

Authors: Mumtaz Ipek, Burak Erkayman

Abstract:

Due date is assigned as an input for scheduling problems. At the same time, due date is selected as a decision variable for real time scheduling applications. Correct determination of due dates increases shop floor performance and number of jobs completed on time. This subject has been mentioned widely in the literature. Moreover rules for due date determination have been developed from analytical analysis. When a job arrives to the shop floor, a due date is assigned for delivery. Various due date determination methods are used in the literature. In this study six different due date methods are implemented for a hypothetical dynamic job shop and the performances of the due date methods are compared.

Keywords: scheduling, dynamic job shop, due date assignment, management engineering

Procedia PDF Downloads 523

Authors: Aydin Teymourifar, Gurkan Ozturk

Abstract:

In this paper, a new hybrid particle swarm optimization algorithm is proposed for the multi-objective flexible job shop scheduling problem that is very important and hard combinatorial problem. The Pareto approach is used for solving the multi-objective problem. Several new local search heuristics are integrated into an algorithm based on the critical block concept to enhance the performance of the algorithm. The algorithm is compared with the recently published multi-objective algorithms based on benchmarks selected from the literature. Several metrics are used for quantifying performance and comparison of the achieved solutions. The algorithms are also compared based on the Weighting summation of objectives approach. The proposed algorithm can find the Pareto solutions more efficiently than the compared algorithms in less computational time.

Keywords: swarm-based optimization, local search, Pareto optimality, flexible job shop scheduling, multi-objective optimization

Procedia PDF Downloads 343