29-09-2016, 11:56 AM
1456761772-workschedulingpaper16.2.16gilli.docx (Size: 251.55 KB / Downloads: 6)
Abstract:A job shop manufacturing system is specifically designed to simultaneously produce different types of products in a shop floor. Job shop scheduling problems (JSSPs) have been studied extensively and most instances of JSSP are NP-hard, which implies that there is no polynomial time algorithm to solve them. As a result, many approximation methods have been explored to find near-optimal solutions within reasonable computational efforts. Furthermore, in a real world, JSSP is generally dynamic with continuous incoming jobs and providing schedules dynamically within constrained computational times in order to optimize the system performance becomes a great challenge.In this paper, Ant Colony Optimization Algorithm (ACO) is proposed to reduce the total completion timeof shop floor projects. In this scheduling, the time is considered as a main factor. The works are scheduled as based on this time factor. Less time consumption of works is scheduled as first order and others are outsourced in this system.The experimental result shows that ACO the average percentage of reduction in makesspan is up to 21.12%.
INTRODUCTION
Scheduling is the decision-making process which deals with the allocation of resources to tasks over time. In the current competitive market environment, companies have to deliver the goods on the date committed to the costumers, using the available resources in the most efficient manner. To achieve these aims, an optimized scheduling, possibly with antagonic goals, is required.
The scheduling methods proposed in the beginning of last century by Henry Gantt, have developed into very sophisticated algorithms, focusing both on deterministic and on stochastic systems. Today, we can find analytical solutions for different scheduling problems, as well as heuristic optimization methods like genetic algorithms (Bean 1994), or market-based-approaches(Wellman et al. 2001), to solve NP-hard problems. However, there are still many topics, both theoretical and practical, which have to be studied in the near future (McKay et al. 2001). One of these topics is the distributed scheduling in manufacturing.
Scheduling of large-scale processes with complex goals and constrains can hardly be done using a centralized scheduler. The decomposition of the problem distributed by different interacting agents in the process, i.e. resources and tasks, can lead to an optimized solution since every participating part contributes with information and suggestions to the final decision. This type of distributed methodology is even more important since the future scheduling policies will have to include online and reactive rescheduling, in order to face different phenomena like production breakdowns or changes in the production planning, imposed by clients or by the market.
In a distributed scheduling problem, the number of agents involved and the quantity of information thathas to be exchanged is very large. Multi-agent algorithms based on social insects, can avoid this complexity. Social insects, e.g. ants, have captured the attention of scientists because of the high structuration level that the colonies can achieve, especially when compared to the relative simplicity of the individuals. Artificial ants are presented in detail in (Dorigo et al. 1996), as the result of preliminary works, where ants were used to solve different types of NP-hard problems. Colorni et al. (1994) and more recently, Cicirello and Smith (2001), have proposed the application of the ant colonies algorithm to solve the jobshop floor problem. Here, we propose a new approach for decentralized scheduling in a parallel machine environment.
In this paper, thecompletion time(C_i) of job iis the time at which processing of the last operationof the job is completed is focused.Theoperational production management, whichdecides the processing of those orders on the shop floor in order to fulfill the orderrequirements, and at the same time, optimizes the performance of the manufacturingsystem. It needs proper scheduling strategies to meet those requirements. Afterscheduling, the schedule is transferred to the shop floor and the implementation of aschedule is often referred to as dispatching.The paper is organized as follows. The next sectiondescribes a typical production system and the limitationsof the schedulers in this type of processes. Then,the principles of the optimization algorithm using antcolonies are introduced, as well as the new frameworkfor the application to scheduling of productionprocesses. Finally, some simulation examples and theanalysis of the results are presented. The closing sectionconcludes this paper and defines the future researchwork.
SCHEDULING IN MANUFACTURING PRODUCTION MANAGEMENT
In many manufacturing and assembly facilities, everyjob can be processed in the same type of machines.This kind of environment, where the machines areset up in parallel is usually referred to as parallelmachines environment (Pinedo 2002). The study ofthis environment is very important from both a theoreticaland a practical point of view: the occurrenceof resources in parallel is common in the real world,e.g. in the flexible flow shopconfigurations, and thetechniques used for machines in parallel are often usedin decomposition procedures for multistage systems.
Dynamic scheduling problems
Scheduling in the real world is dynamic and stochastic in nature. A schedulingproblem is dynamic if there are continuous arrivals of new jobs and stochastic ifuncertain events like machine breakdowns or variant processing times are considered.Those events are introduced into the system due to two factors. Quantities may eitherhave inherent variability or they cannot be measured exactly (Ovacik and Uzsoy,1994, 1997). The main consequence of those uncertainties for a scheduling system isthat a predetermined schedule can become obsolete immediately.In dynamic/stochastic manufacturing environments, managers, production planners,and supervisors must not only generate high-quality schedules but also react promptlyto unexpected events in order to revise schedules in a cost-effective manner. In anattempt to construct an effective reactive scheduling system, various approaches havebeen proposed and they can be categorized as industrial and academic studies.
The essential motivation of the current study is to develop a scheduling system thatcan keep on optimizing the performance of a job shop manufacturing system in realtime in the face of dynamic events.ant colony,has found that autonomous agents like ants can find the shortest route from their nestto a food source based on the pheromone strength on their ways. Each ant affects theenvironment by leaving behind itself some amount of pheromone. This type ofoptimization mechanism is a collective effect of the interactions between the ants andthe pheromone environment. Furthermore, it is also found that an alternative shortestpath can soon be formed by foraging ants if the current one is not available. Bothfeatures are of great research interests in the view of their applications indynamic/stochastic scheduling environments.In order to realize this mechanism for the optimization purpose in schedulingproblems, two implementations had been proposed. One is ACO based scheduling and outsourcing.
3. SCHEDULING USING ANT COLONIES
Ants are social insects. They live in colonies and alltheir actions are towards the survival of the colony asa whole, rather than the benefit of a single individualof the society. The individual ants have no specialabilities. They communicate between each other usingchemical substances, the pheromones. This indirectcommunication allows the entire colony to performcomplex tasks, such as establishing the shortest routepaths from their nests to feeding sources. In (Dorigoet al. 1996) an optimization algorithm was proposedthat tries to mimic the foraging behavior of real ants,i.e. the behavior of wandering in the search for food.This algorithm has already been successfully used tosolve the TSP (Gambardella and Dorigo 1996), andother NP hard optimization problems (Silva et al.2002). The next subsections describe the ant coloniesalgorithm and a new application in scheduling ofproduction systems.
Data collection
In this system, fifteen types of manufacturing tools are considered. The quantity of all tools set to as 5000. Four types of working time are considered for Computer Numerical Control (CNC). Finally the total completion time is calculated. Based on this time factor only scheduling is processed.
General description of the ant colonies algorithm
When an ant is searching for the nearest food sourceand comes across with several possible trails, it tendsto choose the trail with the largest concentrationof pheromone, with a certain probability p. Afterchoosing the trail, it deposits a certain quantityof pheromone, increasing the concentration ofpheromones in this trail. The ants return to the nest usingalways the same path, depositing another portionof pheromone in the way back.
Imagine then, that two ants at the same locationchoose two different trails at the same time. Thepheromone concentration on the shortest way will increasefaster than the other: the ant that chooses thisway, will deposit more pheromones in a smaller periodof time, because it returns earlier. If a whole colonyof thousands of ants follows this behavior, soon theconcentration of pheromone in the shortest path willbe much higher than the concentration in other paths.Then the probability of choosing any other way will bevery small, and only very few ants among the colonywill fail to follow the shortest path. There is anotherphenomenon related with the pheromone concentration.Since it is a chemical substance, it tends to evaporatein the air, so the concentration of pheromonesvanishes along the time. In this way, the concentrationof the less used paths will be much lower than that onthe most used ones, not only because the concentrationincreases in the other paths, but also because their ownconcentration decreases.
In general, the ant colony behavior can be describedformally using the following mathematical framework.Let the nest and the food source be connectedby several different paths, connecting n intermediatenodes. The ant k in node i chooses one of the possibletrails (i,j) connecting the actual node to one of otherpossible positions j∈{1,…,n}, with probability
p_ij^k=f(τ_ij) (1)
Whereτ_ij is the pheromone concentration on the pathconnecting i to j, in the way to the food source.
The pheromone in this trail will vary in time accordingto:
τ_ij (t+1)=τ_ij (t)×ρ+δ_ij^k (2)
Where δ_ij^kpheromone released by the ant kon the trail (i ,j) and ρ∈[0,1] is the evaporationcoefficient. The system is continuous, so the time actsas the performance index, since the shortest pathswill have the pheromone concentration increased in ashorter period of time.
This is the mathematical description of a real colonyof ants. However, the artificial ants that mimic thisbehavior, can be uploaded with more characteristics,e.g. memory and ability to see. If the pheromoneexpresses the experience of the colony in the job offinding the shortest path, memory and ability to see,express useful knowledge about the problem the antsare solving. In this way, (1) can be extended to:
p_ij^k (t)={█((τ_ij^α.η_ij^β)/(∑_(r∉Γ)^n▒〖τ_ij^α.η_ij^β 〗) if j∉Γ@0 otherwise)┤ (3)
Whereη_ij^ a visibility is function and Γ is a work list.In this case, the visibility expresses the capability ofseeing which is the nearest node j to travel towardsthe food source. Γ is a list that contains all the trailsthat the ant has already passed and must not be chosenagain (artificial ants can go back before achieving thefood source). This acts as the memory of an ant. Ifthe TSP is the problem to be solved, the visibilityfunction can be the inverse of the distance from cityi to city j expressed in a matrix d_ij . Then η_ij^ = 1/d_ijand the work list Γ is the list of cities that the ant hasalready visited. The parameters α and β express therelative weight between the importance of pheromoneconcentration τ and the visibilityη. Finally, each antdeposits a pheromone δ_ij^kon the chosen trail:
δ_ij^k=τ_c (4)
where τ_c is a constant.
In the artificial ants framework, equation (2) is notsufficient to mimic the increasing pheromone concentrationin the shortest path. With real ants, time acts asa performance index, but the artificial ants use all thesame time to perform the task, whether they choose ashort path or not. For the artificial ants, it is the length lof the paths they have passed that will determine if thesolution is good or not. Thus the best solution shouldincrease even more the pheromone concentration onthe shortest trail. To do so, (2) is changed to:
τ_ij (t+n)=τ_ij (t)+ρ+∆τ_ij (5)
Where ∆τ_ij are pheromones deposited in the trails(i,j) followed by all the q ants,
∆τ_ij=∑_(k=1)^q▒〖δ_ij^k×f(1/z_k ) 〗 (6)
And z_k is the performance index. In the CNC case thez_k can be the length l_k=∑▒d_ij of the path chosenby the k ant. In this way, the global update is biasedby the solution found by each individual ant. Thepaths followed by the ants that achieved the shortestpaths have their pheromone concentration increased.Notice that the time interval taken by the q ants to do acomplete tour is t + n iterations. A tour is a completeroute between the nest and the food source and iterationis a step from i to j done by all the ants.The algorithm runs N_max times, where in every N^thtour, a new ant colonyis released. The total number ofiterations is N_max × n. The general algorithm for theant colonies is described