The production planning in both the molding and customizing processes is made separately. In the molding process it is made based on demand forescast provided by the comercial department for a specific planning horizon. As mentioned before, this study focuses on the planning decisions in the molding process. This production environment usually comprises several parallel machines, to which all the possible molding patterns can be attached. The main decisions include defining which molding pattern to attach to each molding machine, how long each molding pattern should be used and what sequence they should follow.
Besides that, minimum and maximum inventory target levels must be considered, since there are penalties costs associated to the deviation from these levels. As several products can be produced simultaneously by different production rates, the inventory levels must be carefully managed in order to avoid producing high levels of low demand products and backlogs of high demand products.
To avoid solutions of this type, minimum and maximum inventory target levels are defined according to the demand of each product and penalties are defined for eventual deviations from these levels. Changeovers between molding patterns imply sequence-dependent setup times and costs. In this industry, setup times are triangular and can take from 30 minutes up to 48 hours. Besides that, setup operations also require specialized labour which increase significantly the setup costs. In this way, all decisions about lot sizing and sequencing molding patterns must be made in order to minimize the total setup and inventory holding costs, as well as penalties associated to deviation from the inventory target levels.
The mathematical approach proposed to represent the studied problem is based on the classical GLSP formulation proposed by Meyr and Ferreira et al. It considers a set of parallel machines which have the same technical characteristics, speed, and setup times. It is assumed that each machine can use any of the possible molding patterns at any time. Each time period represents a week of the planning horizon so that each one is divided into several sub-periods of variable sizes.
Only one molding pattern can be set up and used in each sub-period. Parameters such as total capacity and the production rate of each molding pattern are provided in hours. Setup times and costs are triangular and sequence-depedent. The setup state is preserved between time periods, so it is considered as setup carry-over. L Total machines. S t Total sub-periods in period t. I k 0 Initial inventory level of product k. I k min Minimum inventory target level of product k. I k max Maximum inventory target level of product k.
Q l t Capacity of machine l in period t hours. M l i t Upper bound for variable x l i s. I k t Inventory of product k at the end of period t. The objective function 1 minimizes the total costs involved, which comprise the inventory holding costs, setups costs, as well as penalties associated to deviations from the inventory target levels.
Constraints 2 are the demand balance constraints, which relate the quantities produced the inventory levels and the demand. Differently from the other classical formulations for lot sizing and scheduling problems, the lots of products are obtained by parts, each part by using a specific molding pattern. Thus, there is not just one lot of products in each period, but there is only one lot of process represented by the production time of each molding pattern. Constraints 3 are about the capacity consumption in each time period. Note that capacity is consumed by production times of each molding pattern and setup times.
Constraints 4 guarantee that a molding pattern is used if, and only if, the machine is set up to this in sub-period s. As backlogs are not allowed, if molding pattern i is used, the maximum production time in each period is at most M l i t , which may be approximated to equation Equations 12 determine an upper bound for the production time of each molding pattern in each period.
In this way, each molding pattern may use at most the total capacity of the period, or the time required to meet the remaining demand of the products that are produced by this pattern. The capacity of machine l in period t is hours and the remaining demand is , units of product A and 1,, units of product B. It means that this molding pattern will be used at most for 40 hours in the production line l in period t. Constraints 5 guarantee that each machine is set up to only one molding pattern in each sub-period.
Constraints 6 , 7 and 8 relate the setup states between two consecutives sub-periods, so that they determine changeovers and preserve the setup state. Inequalities 9 and 10 determine how many units of each product are out of the inventory target levels, in each period.
Finally, 11 defines the type of variable of the problem. Note that the production time of each molding pattern is a positive variable. Although this does not guarantee that the amount of products are integer quantities, this approximation is acceptable in this production environment, since production volumes are large and minimum inventory levels are defined. The experiments comprise several instances based on real data provided by a Brazilian plant. A single instance was used to compare production plans provided by solving the model and by the production planner of the company.
Other computational tests were executed for 12 real instances and other random instances in order to analyze the performance of the model. Besides the parameters of the problem, for this instance the initial setup states of the machines and the maintenance activities scheduled over the planning horizon were considered. The number of sub-periods was defined based on the maximum number of changeovers defined by the company, ideally up to 4 per period.
The limit elapsed time to solve the model is 3 hours. The results provided by the GLSP model for this instance define a schedule plan which specifies the molding patterns to be used over the planning horizon and how long each one is used. Table 2 presents some information about the amount of products produced over the planning horizon, the total inventory at the end of the planning horizon and the deviations from the inventory target levels.
Hybrid Metaheuristics for Solving a Fuzzy Single Batch-Processing Machine Scheduling Problem
Note that the main advantages of the schedule provided by solving the proposed model are related to the capacity consumption, reductions of the total setup times and control of the inventory levels. Although this reduction is not much over the one-month planning horizon, it has a better effect on the total setup costs, since setup costs in this company are quite high. Note that the model solution meets all the demand without backlogs.
However, the company solution does not meet the demand of , units at the end of the planning horizon. This evidences how hard it is to choose and schedule molding patterns so that demand requirements are fully met. In general, the model solution produced a lower quantity of products and inventory levels at the end of the planning horizon. It suggests that the model solution manages inventory and production levels in a better way than the company schedule, so that in this solution the inventory levels are closer to the target levels.
Note that in the company schedule Meanwhile in the schedule provided by solving the model it is only Some of the advantages of the model solution related to the costs involved are illustrated in Figure 2 , which presents the total costs for each schedule. In the same way inventory holding costs are also reduced about To analyze the performance of the GLSP model, a set of 12 instances was created based on real information provided by the company.
These instances represent real data related to the number of products, possible molding patterns, production rates of each molding pattern, inventory target levels, setup times and costs, and other parameters, as presented in Table 3. The 12 instances represent demand requirements for 12 different months of 4 weeks each. The production environment comprises 3 machines available 7 days per week, 24 hours per day. The number of sub-periods in each period was defined based on the maximum number of changeovers desired by the planners, so that each period has 4 sub-periods.
Each instance comprises information about demand and initial inventory level for 14 products, which can be obtained by 19 different molding patterns, as Table 4 shows. Table 5 presents the results of the model after 3 hours. This table shows the incumbent solution after the limit time, the best upper bound, the gap provided by CPLEX, total elapsed time and the approximated time that the incumbent solution was found.
As a general remark, the model was able to find feasible solutions for all the instances. However, its performance is not uniform for all of them, so that in some cases optimal solutions are found and in others the solutions have a high gap. Among the instances which were not solved optimally, some solutions have a gap less than 6. However, instances 1 and 10 were not easy to solve, since the incumbent solutions have gaps of Note in the last column of Table 5 that, on average, the model gets the best solution in the first minutes for most of the instances.
However, sometimes it spends a lot of time improving lower bounds. To make a better analysis of the model performance, some random instances were also tested. The characteristics of these random instances are presented in Table 6 and the results in Table 7. Note that these instances are smaller in size than the real instances provided by the studied company. Results show than the proposed model is able to provide feasible solutions for all the instances. However, optimal solutions only were found in the smaller size groups 1 and 2, which comprise only 2 machines, 6 molding patterns, 5 products, and 5 time periods.
It is worth mentioning that in the random instances the number of sub-periods for each period was determined as the number of possible molding patterns, i. Thus, it evidences that the model performance depends, among other parameters, on the number of sub-periods which is determined in advance.
- The Strange Case of Mr. Nobody.
- Pareto, Economics and Society: The Mechanical Analogy (Routledge Studies in the History of Economics).
- Blood and Ice.
This parameter can be defined either based on the experience of the planner or by preliminary computational experiments. This paper studied the production planning and scheduling in molding packaging industry by particularly considering the production environment of a Brazilian company which produces packages for fruit and eggs. The planning decisions are related to the selection of molding patterns, how long they are used, and how they are sequenced.
Results of the computational tests showed that it is possible to find feasible solutions for all the instances by solving the model by CPLEX. That suggests exploring alternative formulations that do not depend on parameters defined in advance, which can influence the performance of the model. All these advantages are evidenced in a reduction of Almada-Lobo, B. Production planning and scheduling in the glass container industry: AVNS approach. International Journal of Production Economics, 1 , Araujo, S.
Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups.
Journal of Heuristics, 13 4 , Augusto, D. In press. Clark, A. Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching. Journal of Scheduling, 13 2 , Drexl, A. Lot sizing and scheduling - Survey and extensions. European Journal of Operational Research, 99 2 , Ferreira, D. Operations Management. Scheduling is essentially the short-term execution plan of a production planning model.
Production scheduling consists of the activities performed in a manufacturing company in order to manage and control the execution of a production process.
Product | Metaheuristics for Scheduling in Industrial and Manufacturing Applications
Detailed scheduling is essentially the problem of allocating machines to competing jobs over time, subject to the constraints. Each work center can process one job at a time and each machine can handle at most one task at a time. A scheduling problem, typically, assumes a fixed number of jobs and each job has its own parameters i. All scheduling approaches require some estimate of how long it takes to perform the work. Scheduling affects, and is affected by, the shop floor organization. All scheduling changes can be projected over time enabling the identification and analysis of starting time, completion times, idle time of resources, lateness, etc….
A right scheduling plan can drive the forecast to anticipate completion date for each released part and to provide data for deciding what to work on next. The aim of a scheduling study is, in general, to perform the tasks in order to comply with priority rules and to respond to strategy.
An optimal short-term production planning model aims at gaining time and saving opportunities. It starts from the execution orders and it tries to allocate, in the best possible way, the production of the different items to the facilities. A good schedule starts from planning and springs from respecting resource conflicts, managing the release of jobs to a shop and optimizing completion time of all jobs.
It defines the starting time of each task and determines whatever and how delivery promises can be met. The minimization of one or more objectives has to be accomplished e. Criteria could be ranked from applying simple rules to determine which job has to be processed next at which work-centre i.
Fortunately many of these objectives are mutually supportive e. To identify the exact sequence among a plethora of possible combinations, the final schedule needs to apply rules in order to quantify urgency of each order e. Rules combined into heuristic  - approaches and, more in general, in upper level multi-objective methodologies i. In the past few years, metaheuristics have received much attention from the hard optimization community as a powerful tool, since they have been demonstrating very promising results from experimentation and practices in many engineering areas.
Therefore, many recent researches on scheduling problems focused on these techniques. Mathematical analyses of metaheuristics have been presented in literature [ 2 , 3 ]. This research examines the main characteristics of the most promising meta-heuristic approaches for the general process of a Job Shop Scheduling Problems i. Being a NP complete and highly constrained problem, the resolution of the JSSP is recognized as a key point for the factory optimization process [ 4 ].
The chapter examines the soundness and key contributions of the 7 meta-heuristics i. It reviews their accomplishments and it discusses the perspectives of each meta approach. The work represents a practitioner guide to the implementation of these meta-heuristics in scheduling job shop processes. It focuses on the logic, the parameters, representation schemata and operators they need. Cox et al. Pinedo listed a number of important surveys on production scheduling [ 8 ]. Makowitz and Wein classified production scheduling problems based on attributes: the presence of setups, the presence of due dates, the type of products.
Practical scheduling problems, although more highly constrained, are high difficult to solve due to the number and variety of jobs, tasks and potentially conflicting goals. Recently, a lot of Advanced Production Scheduling tools arose into the market e. Each of these automatically reports graphs.
Their goal is to drive the scheduling for assigned manufacturing processes. They implement rules and optimise an isolated sub-problem but none of the them will optimise a multi stage resource assignment and sequencing problem. In a Job Shop i. In this contest, each job has its own individual flow pattern through assigned machines, each machine can process only one operation at a time and each operation can be processed by only one machine at a time.
The purpose of the procedure is to obtain a schedule which aims to complete all jobs and, at the same time, to minimize or maximize the objective function. Mathematically, the JS Scheduling Problem i. It has been generally shown to be NP-hard  - belonging to the most intractable problems considered [ 4 , 11 , 12 ].
This means that the computation effort may grow too fast and there are not universal methods making it possible to solve all the cases effectively. Just to understand what the technical term means, consider the single-machine sequencing problem with three jobs. How many ways of sequencing three jobs do exist? Only one of the three jobs could be in the first position, which leaves two candidates for the second position and only one for the last position. Therefore the no. Thus, if we want to optimize, we need to consider six alternatives. This means that as the no.
Scheduling, however, performs the definition of the optimal sequence of n jobs in m machines. If a set of n jobs is to be scheduled on m machines, there are n!
- Metaheuristics for Scheduling in Industrial and Manufacturing Applications?
- Lot sizing and scheduling in the molded pulp packaging industry?
- Citations per year!
- International Journal of Research in Industrial Engineering - Editorial Board.
- Metaheuristics for Scheduling in Industrial and Manufacturing Applications!
It has to undergo a discrete number of operations i. Each product has a fixed route defined in the planning phase and following processing requirements i. Other constraints, e. Each machine can process only one operation at a time with no interruptions pre-emption. The schedule we must derive aims to complete all jobs with minimization maximization of an objective function on the given production plant.
To accommodate extreme variability in different parts of a job shop, schedulers separate workloads in each work-centres rather than aggregating them [ 14 ]. Besides these, Makespan is often the performance feature in the study of resource allocation [ 16 ]. Makespan represents the time elapsed from the start of the first task to the end of the last task in schedule. The minimisation of makespan arranges tasks in order to level the differences between the completion time of each work phase.
It tries to smooth picks in work-centre occupancy to obtain batching in load assignment per time. The possible representation of a JS problem could be done through a Gantt chart or through a Network representation. Gantt created innovative charts for visualizing planned and actual production [ 18 ].
According to Cox et al. Gantt designed his charts so that foremen or other supervisors could quickly know whether production was on schedule, ahead of schedule or behind schedule. A Gantt chart, or bar chart as it is usually named, measures activities by the amount of time needed to complete them and use the space on the chart to represent the amount of the activity that should have been done in that time [ 7 ]. A Network representation was first introduced by Roy and Sussman [ 20 ].
Tasks are defined in a network representation through a probabilistic model, observing the precedence constraints, characterized in a machine occupation matrix M and considering the processing time of each tasks, defined in a time occupation matrix T. The descriptions and notations as follow are due to Adams et. V is a set of nodes representing tasks of jobs. C is the set of conjunctive arcs or direct arcs that connect two consecutive tasks belonging to the same job chain. These represent technological sequences of machines for each job;. In this representation all nodes are weighted with exception of source and sink node.
A graph representation of a simple instance of JSP, consisting of 9 operations partitioned into 3 jobs and 3 machines, is presented in fig. Let s v be the starting time of an operation to a node v. By using the disjunctive graph notation, the JSPP can be formulated as a mathematical programming model as follows:. Disjunctive graph representation. There are disjunctive arcs between every pair of tasks that has to be processed on the same machine dashed lines and conjunctive arcs between every pair of tasks that are in the same job dotted lines.
Job notation is used. The second condition ensures time to start continuities. In order to obtain a scheduling solution and to evaluate makespan, we have to collect all feasible permutations of tasks to transform the undirected arcs in directed ones in such a way that there are no cycles.
While the total number of arcs, in job notation, is fixed considering the number of tasks and jobs of instance:. The number of arcs defines the possible combination paths. Each path from source to sink is a candidate solution for JSSP. The routing graph is reported in figure 2 :.
A logic has to be implemented in order to translate the scheduling problem into an algorithm structure. Academic researches on scheduling problems have produced countless papers [ 23 ]. Scheduling has been faced from many perspectives, using formulations and tools of various disciplines such as control theory, physical science and artificial intelligence systems [ 24 ]. Criteria for optimization could be ranked from applying simple priority rules to determine which job has to be processed next at the work-centres i. Guidelines in using heuristics in combinatorial optimization can be found in Hertz [ 27 ].
A classification of heuristic methods was proposed by Zanakis et al. The first ones are focused on producing a solution based on an initial proposal, the goal is to decrease the solution until all the jobs are assigned to a machine, not considering the size of the problem [ 29 ]. The second ones are iterative algorithms which explore solutions by moving step by step form one solution to another.
The method starts with an arbitrary solution and transits from one solution to another according to a series of basic modifications defined on case by case basis [ 30 ]. Relatively simple rules in guiding heuristic, with exploitation and exploration, are capable to produce better quality solutions than other algorithms from the literature for some classes of instances. These variants originate the class of meta-heuristic approaches [ 31 ]. The meta-heuristics  - , and in general the heuristics, do not ensure optimal results but they usually tend to work well [ 32 ].
The purpose of the paper is to illustrate the most promising optimization methods for the JSSP. As optimization techniques, metaheuristics are stochastic algorithms aiming to solve a broad range of hard optimization problems, for which one does not know more effective traditional methods. Often inspired by analogies with reality, such as physics science, Simulated Annealing [ 33 ] and Electromagnetic like Methods [ 34 ], biology Genetic Algorithms [ 35 ], Tabu Search [ 36 ] and ethnology Ant Colony [ 37 ,], Bees Algorithm [ 38 ] , human science Neural Networks [ 39 ] , they are generally of discrete origin but can be adapted to the other types of problems.
The methodology of a GAs - based on the evolutionary strategy- trasforms a population set of individual objects, each with an associated fitness value, into a new generation of the population occurring genetic operations such as crossover sexual recombination and mutation fig. The theory of evolutionary computing was formalized by Holland in [ 40 ]. The theory of evolution is biologically explained, the individuals with a stronger fitness are considered better able to survive..
Cells, with one or more strings of DNA i. The gene i. Physical manifestations are raised into genotype i. Each genotype has is physical manifestation into phenotype. According to these parameters is possible to define a fitness value. Combining individuals through a crossover i. In each epoch a stochastic mutation procedure occurs. The implemented algorithm is able to simulate the natural process of evolution, coupling solution of scheduling route in order to determinate an optimal tasks assignment.
Generally, GA has different basic component: representation, initial population, evaluation function, the reproduction selection scheme, genetic operators mutation and crossover and stopping criteria. Central to success of any GA is the suitability of its representation to the problem at hand [ 42 ].
This is the encoding from the solution of the problem domain to the genetic representation. It uses sequence of repeated jobs identifier e. According to the instance in issue, each of the N jobs identifiers will be repeated M times, once for each task. In this way, precedence constraints are satisfied. The redundancy is the most common caveat of this representation. The Genetic Algorithms GAs model; 3a. A mutation operator is applied changing the genes into the same genotype in order to generate only feasible solutions, i.
Mutation allows to diversify the search over a broader solution domain and it is needed when there is low level of crossover. Among solutions, the allocation with favourable fitness will have higher probability to be selected through the selection mechanisms. Another important issue for the GA is the selection mechanism e.
The tournament selection procedure is based on analogy with competition field, between the genotypes in tournament, the individual which will win e. It is very important, for the GAs success, to select the correct ratio between crossover and mutation, because the first one allows to allows to diversify a search field, while a mutation to modify a solution. If we are on a pic-nic and peer into our cake bitten by a colony of ants, moving in a tidy way and caring on a lay-out that is the optimal one in view of stumbling-blocks and length, we discover how remarkable is nature and we find its evolution as the inspiring source for investigations on intelligence operation scheduling techniques [ 45 ].
Natural ants are capable to establish the shortest route path from their colony to feeding sources, relying on the phenomena of swarm intelligence for survival. They make decisions that seemingly require an high degree of co-operation, smelling and following a chemical substance i. The same behaviour of natural ants can be overcome in an artificial system with an artificial communication strategy regard as a direct metaphoric representation of natural evolution.
Artificial ants are quite different by their natural progenitors, maintaining a memory of the step before the last one [ 37 ]. The initial schedule is constructed by taking into account heuristic information, initial pheromone setting and, if several routes are applicable, a self-created selection procedure chooses the task to process. The same process is followed during the whole run time. The probabilistic approach focused on pheromone.
The approach focuses on co-operative ant colony food retrieval applied to scheduling routing problems. Colorni et al, basing on studies of Dorigo et al. They iteratively create route, adding components to partial solution, by taking into account heuristic information on the problem instance being solved i.
Across the representation of scheduling problem like acyclic graph, see fig. Think at ants as agents, nodes like tasks and arcs as the release of production order. According to constraints, the ants perform a path from the row material warehouse to the final products one. Constraints are introduced hanging from jobs and resources.
Fitness is introduced to translate how good the explored route was. Artificial ants live in a computer realized world. They have an overview of the problem instance they are going to solve across a visibility factor. A probability is associated to each feasible movement S ant t and a selection procedure generally based on RWS or Tournament procedure is applied. For each cycle the agents of the colony are going out of source in search of food.
When all colony agents have constructed a complete path, i. These parameters imitate the natural world decreasing of pheromone trail intensity over time. It implements a useful form of forgetting. It has been considered a simple decay coefficient i. The laid pheromone on the inquired path is evaluated taking into consideration how many agents chose that path and how was the objective value of that path Eq. The weight of the solution goodness is the makespan i. A constant of pheromone updating i. The algorithm works as follow. It is evaluated and laid, according to the disjunctive graph representation of the instance in issue, the amount of pheromone on each arc evaporation coefficient is applied to design the environment at the next step.
Visibility and updated pheromone trail fixes the probability i. An objective function value is optimised accordingly to partial good solution. A colony of bees exploits, in multiple directions simultaneously, food sources in the form of antera with plentiful amounts of nectar or pollen.
They are able to cover kilometric distances for good foraging fields [ 50 ]. Flower paths are covered based on a stigmergic approach — more nectar places should be visited by more bees [ 51 ]. The foraging strategies in colonies of bees starts by scout bees — a percentage of beehive population. They wave randomly from one patch to another. Returning at the hive, those scout bees deposit their nectar or polled and start a recruiting mechanism rated above a certain quality threshold on nectar stored [ 52 ]. The recruiting mechanism is properly a launching into a wild dance over the honeycomb.
Bees, stirring up for discovery, flutter in a number from one to one hundred circuits with a waving and returning phase. The waving phase contains information about direction and distance of flower patches.