Job Shop Scheduling Problem
with Heuristic Genetic Programming Operators
This paper introduces an optimization algorithm for job shop scheduling problem in logistic warehouses. The algorithm is based on genetic programming and uses parallel processing. For better performance a new optimization method called ”priority rules” were proposed. We found out that the three proposed priority rules help algorithm to prevent to stuck in local optima and to get better results from genetic programming optimization. Algorithm was tested with batch of tests based on data from real warehouse and with synthetic tests generated randomly (inspired with the real world scenarios). Results indicate interesting reduction of time that is necessary to fulfill all tasks in warehouses, reduction in number of collisions and better optimization performance.
@inproceedings{povoda2015job,
title={Job shop scheduling problem with heuristic genetic programming operators},
author={Povoda, Lukas and Burget, Radim and Masek, Jan and Dutta, Malay Kishore},
booktitle={2015 2nd International Conference on Signal Processing and Integrated Networks (SPIN)},
pages={702--707},
year={2015},
organization={IEEE}
} Introduction
Business process optimization is one of the most difficult problems, which is falls into so-called NP-hard problem class. In warehouses, the work is in general divided into tasks that are managed by operation manager. Every worker can have different license to different vehicles and equipment, different experience and performance, work of one worker is often prerequisite to another work, location of one task can be in different area of the warehouse, some vehicles can do only a specified kind of jobs (e.g. put the palette in 7th floor) and many others. The operation manager needs to have experience and detailed knowledge of the warehouse. They must take into account many aspects and estimate many future events that can have impact on future large numbers of data that can have an impact on the final time of work. Because this, it can be often quite complicated and also time–consuming to resolve this problem using computer problems. On the other hand, when there is large number of tasks and the operation of the warehouse becomes very complex, computer can equal or outperform human competitors, can be more reliable in time of overload, is resistant to panic and can be also cheaper, faster and more flexible, when deployed appropriately. The main objective of the optimization algorithms is to decide the order of tasks, assign the tasks to person and tell the workers which equipment they will use in order to fulfil the given tasks as soon as possible with minimal possible demands to human resources (workers) and balanced load on the workers, i.e. maximal production performance.
This paper deals with the business process optimization using genetic programming, which is relatively successful method for complex problem solving but quite computationally consuming, especially for complex problem solving. The paper builds on the previous work [1], [2] and introduces an optimized heuristic method, which we call priority rules and which can be combined with evolutionary methods like genetic programming. According to our experiments, paralellization of the genetic programming have had significantly lower impact on the resulting accuracy than deployment of the priority rules and stacked in local optima. It was experimentally proven, that combination of an evolutionary based method (genetic programming) and heuristic method (the priority rules) had significant impact on the resulting accuracy and quality of proposed solutions.
The main contribution of this paper is a new heuristics operators for business process optimization, those operators are called priority rules, which can be used in the genetic programming algorithm. These rules provides prediction about search space, where it is expected that more accurate solution can be found. We have evaluated the method on the real world test-cases and also on extended artificially generated test-cases (inspired from the previous real world examples) and we have proven that results are more accurate (12.7% better in case with 50 tasks) with lower computation load.
The rest of the paper is structured as follows. Section II describes related work and existing methods and solutions for job shop optimization problem. The section also tries to compare the introduced method with these works. Section III describes experiment that was conducted in order to validate accuracy of the algorithm, it also describes basics of genetic programming and the proposed algorithms. Section IV describes rules and defines how they were proposed and why. Section V provides experimental results and discussion about the results. The section compares also the achieved results and optimal settings of the algorithm for the given extent of solved task, behaviour of the fitness function. The paper is concluded in section VI.
Related Work
So far there is a lot of work devoted to business process optimization. Despite this fact in many areas of industry these methods failed to be deployed in real production. One of the main cause of this is that the methods are too much theoretical and are not able to perform well in real scenarios and also that they cannot scale well for real world problem complexity with many exceptions, additional rules etc. In paper [3] authors tries to solve the problem with mathematical methods. The disadvantage of this method can be that occurrence of many conditions and exceptions to these conditions (which often brings real world scenarios) lead to conflicts and mathematical description would be very complex and uneconomic, since this description have to be the designed separately for each warehouse. Some of the problems with the mathematical approaches can be found also in [4], [5] and [6]. On the other hand, these methods are quite suitable for not so complex problems as can be read in the paper [7].
Expert systems can generate significantly more complex heuristics. System using expert system can be found for example in [8], and its variant using load distribution on several machines [9] is quite promising in terms of results. The disadvantage of this approach are difficulties with providing appropriate data, their validation, management and further changes or their extension.
The third category of methods are search space methods, which achieves currently one of the most interesting results. Representatives of the search space methods there are e.g. [10], [11] and [12]. Genetic programming as the core optimization algorithm allows to create fully modular system with possibility to extent the system without any additional significant costs. Papers [1] and [2] explains basic principles of utilizing genetic programming for job shop scheduling problem and utilizes so called grammar driven genetic programming in order to make search space smaller and with less inconsistent or invalid candidate solutions. Since the solved problem is still very complex problem (NP-hard), it happens quite often, that the optimization algorithm gets stuck in a local optima. These papers rely only on standard grammar driven genetic programming and they do not utilize any further heuristics to help the algorithm perform better. Also some of the experiments did not outperform human expert.
Experiment Description
This section will describe the data used for algorithm tuning and also for evaluation of the results on independent experiment. This section also describes the genetic programming algorithm, which extends the algorithm by grammar and here introduced heuristics in the form of priority rules.
Train and Test Data Description
In order to be possible evaluate the proposed algorithm, a set of evaluation tests was created. These tests were inspired by selected real world scenarios of a logistic warehouse. These test cases were evaluated by a human expert and is composed of a set of tasks that have to be fulfilled by workers employed in the warehouse. Using these tests, the algorithms were evaluated and compared to human performance, i.e. if the algorithm is worse, equals or is better than the human expert, see [1] and [2].
Those use-cases were divided into 5 different levels according of their complexity and how difficult it is to find an efficient solution for the human expert. The lowest level of use cases contains only one kind of vehicles (handcart in this cases). Since they are easy to be understood by a human. They are used especially for algorithm validation for possible mistakes and errors in algorithm. The highest level contains complex (real world) use-cases with many possibilities, conditions, exceptions and settings including different kind of vehicles with possibility to create collisions in a warehouse aisle, with many features taken into consideration (e.g. lift height). More information about the warehouse model is given in the paper [1].
In order to evaluate the performance on bigger number of use-cases, also some artificially generated test-cases were generated. These tests are inspired by the real world scenarios and are using various settings in terms of number of workers, vehicles, tasks, kinds of vehicles, position of goods etc. This will lead to more reliable evaluation of the processes.
Evolutionary Optimization Algorithm
The algorithm of genetic programming represents a evolutionary part of the solution. State space is searched randomly and getting a globally optimal result is quite challenging. The main advantage of genetic programming is to solve problems where the other algorithms usually ends in a local optima. A solution, which is a local optima is not always bad (or worse than a human expert can propose), but there is a need to minimalize the final time for fulfil every tasks and monitor other parameters (e.g. number of delays and collisions in the warehouse), so this solution can be insufficient.
Search of the state space in genetic programming is powered by so called genetic operators. The algorithm is inspired by Darwin theory of biological evolution, i.e. partial randomness (mutation) and inheritance, combining of the features (crossover of candidate solutions from the one set of candidate solutions to a newly created set of candidate solutions) and natural selection (selection of those candidates for crossover, which are the most promising to find best results). If this theory is applied to the problem, which is solved in this paper, there can be introduced a couple of specific genetic operators, which can make the evolution more effective: a) an operator for change path through the warehouse, i.e. the worker will use another route to fulfil his/her task, b) operator for reordering of jobs in one workplan, i.e. to do the given tasks in different order, c) operator for swapping workplans between two workers, i.e. assign the job to a person, which can be more skilled to do the task list, d) swapping jobs between two workplans, i.e. changing jobs between workers, and e) splitting a job into two or more sub-jobs, i.e. establish a cooperation between workers to fulfil a single job. This is especially beneficial in cases where one vehicle is suitable for transfer of goods but other vehicle is suitable to put a goods palette into higher levels of shelf, so the cooperation of two different forklifts can lead to more effective work. All mentioned genetic operators were described in detail including evaluation test and their results in [1] and [2].
Since the genetic programming is quite computationally demanding and even paralellization of some parts of the algorithm have not lead to optimal results, it was necessary to improve the algorithms with some kind of additional heuristics. This heuristics was implemented using two additional operators: dispatching rules operator and priority rules operator. Those two operators are introduced in the next sections.
Priority Rule Heuristics Operator
The Priority Rules is an algorithm, which we call a heuristic part of algorithm. This is a set of simple rules inspired on the way of thinking of human experts in warehouses. It clearly defines what steps lead to better solutions when we look up on some individual in current step of evolution, i.e. one possible solution. The candidate solution is in this step mutated to suit better to the specific rules and if it provides better results, it will have a higher probability to be used in the crossover operators in future to create new crossovered candidate solutions.
The rule can be applied in different parts of the genetic programming algorithm. According to empirical experimentation it was found that the optimal location of this rule is at the end of cycle of one generation, while this step is performed only every n-th generation, where value of n it is recommended to be in the interval interval <2,5> according to the complexity of the test case. This means that every n-th generation has some chance of appearance in the population of several new set candidate solutions, depending on the number of priority rules.
As already mentioned in the previous chapter, static part of algorithm often helps to get a better solution. In some cases, one genetic programming cycle last longer, but the resulting performance of the algorithm have been found to give approximately twice as good results as the original algorithm was able to give.
Proposed Heuristic Operators
The rules were proposed on the basis of inspiration from dispatching rules and priority rules defined in the article [13]. The last rule was tailored for a specific problem solving of warehouses.
Restricted Swappings Heuristics Operator
From the point of view of the genetic programming algorithm, this rule reorders the tasks in the work plans of a worker using a heuristics. These reordered candidate solutions enter as to the new population with an attempt to firstly process the tasks with the longest distance from start to finish. What should be mentioned here is that the rule does not take into consideration the actual position of the worker neither the distance of a worker to the place where the assigned job should start (e.g. position of a goods palette, where it should be picked up). Of course further evolution and other operators can be used in order to find a compromise between locality and priority of the tasks (risk they will not be fulfilled on time).
To evaluate an impact of the restricted swappings rule on the resulting optimization convergence speed, a testbench was created. In the tests that the testbench contains the rule is being applied immediately after initialization of the candidate solutions (population) and resulting convergence speed and effectiveness were evaluated. For the evaluation we chose a set of real tests (i.e. the most complex ones) each value computed as an average from five runs of each test-case. The values were compared with the results, which were achieved for the test immediately after the initialization (not used genetic programming yet).
Shortest Processing Time Heuristics Operator
Another rule applied for a problem of work control in the logistics warehouse is the Shortest Processing Time (SPT) operator. Rule’s objective is to give preference to tasks with the shortest time required for processing. There is therefore a preference to those tasks, which are closest to the worker and at the same time it has shortest time for its successful completion.
In the table II the tests on which this rule had a positive impact were shown. Those examples shows results without any genetic programming optimization and when used with the genetic programming, it is a promise for even more interesting results.
Fast ForkLift Heuristics Operator
The last rule implemented into the genetic programming algorithm is a rule based on experience of human experts. The rule is supposed to assign the tasks with a long transportation distances to a fast vehicles, while there is an assurance that there wont be an overload of one fast vehicle, but that the load will be evenly distributed on vehicles with a priority to those with faster speed. With the application of this rule there would be a reassurance that the handcarts with a lower speed would take the goods just for shorter distances.
The rule achieves the best results among the implemented rules. With a simple usage of the rule immediately after the initialization of population it is possible to achieve an improvement in average of 5%, while in some tests the improvement of the resulting time was increased by almost 15%.
Results and Discussion
The evaluation of the effect of the introduced rules all together in combination with the genetic programming algorithm was conducted in three different configurations: a) usage of the rules only at the end of the evolution, i.e. in the 20 th generation b) application of the rules every 5 th generation c) application of the rules every 2 nd generation The tests were launched with an optimal setting of a probability of genetic operators (see table IV). Next testing was aimed at cases where the usage of the setting was with worse previous results (see table V).
When comparing the results it is possible to find out that the usage of priority rules achieves greater improvement in inappropriate settings of probability of genetic operators. In practice, priority rules help us to cover the inappropriate setting of probability of genetic operators for a particular task size.
In the figure 4 the value of fitness during the genetic programming optimization process is depicted. In the figure the best candidate solution in the given generation is used. For its evaluation a synthetically generated test were used and two experiments were conducted: with the extended heuristics operators and without the heuristics operators. Both experiments has started with the same initial set of candidate solutions. From the chart it is obvious, that the initial convergence of the optimization algorithm is relatively better in the initial time of the algorithm without the heuristics operators. On the other hand there can be seen that it has got stacked in local optima - i.e. from the 5 th generation the genetic programming was not able to find a better solution. With using of the heuristics operators every second run of the evolution the algorithm was able to continuously optimize the results and is less prone to get stacked in local optima. The final optimized solution achieves much shorter time needed for fulfilling the tasks by workers.
Conclusion
This paper was involved in the optimization of logistic warehouses using genetic programming algorithm and extends the standard genetic programming operators with several newly introduced heuristics operators. The proposed operators were tailored for a specific problem of logistics warehouses. At the end of the article the results of individual measurements reflecting an impact of priority rules on searching the state space are compared with the previous results without those optimizations. The main contribution of this paper is a finding, that the proposed evolutionary and heuristic optimization operators can significantly increase (about 12% better result in the same time) convergence speed of the genetic programming algorithm in the area of process optimization in warehouses. The idea can be also deployed to other problems of the similar type whose solution is based on the genetic programming.
References
- J. Karasek, R. Burget, V. Uher, M. K. Dutta, Y. Kumar. Optimization of logistic distribution centers process planning and scheduling. In: Contemporary Computing (IC3), 2013 Sixth International Conference on. IEEE, 2013. p. 343–348.
- J. Karasek, R. Burget, L. Povoda. Logistic warehouse process optimization through genetic programming algorithm. In: Modern Trends and Techniques in Computer Science. Springer International Publishing, 2014. p. 29–40.
- A. Jones, L. C. Rabelo and A. T. Sharawi, Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering, 1999.
- J. Shapiro, A survey of Lagrangian techniques for discrete optimization. Annals of Discrete Mathematics, 1979, 5.1979: p. 113–138.
- N. Agin, Optimum seeking with branch and bound. Management Science, 1966, 13.4: p. 176–185.
- E. L. Lawler, D. E. Wood, Branch and bound methods: a survey. Operations research, 1966, 14.4: p. 699–719.
- K. Bulbul, P. Kaminsky, A linear programming-based method for job shop scheduling, Journal of Scheduling, vol. 16, no. 2, pp. 161–183, 2013.
- M. S. Fox Constraint-directed search. 1983. PhD Thesis. Carnegie-Mellon University.
- W. Shen, L. Wang, Q. Haq, Agent-based distributed manufacturing process planning and scheduling: a state-of-the-art survey. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 2006, 36.4: p.563–577.
- P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra, Job shop scheduling by simulated annealing, Operations Research, vol. 40, pp. 113–125, 1992.
- E. Nowicki, and C. Smutnicki, An advanced tabu search algorithm for the job shop problem, Journal of Scheduling, vol. 8, pp. 145–159, 2005.
- M. Tasgetiren, Y.-C. Liang, M. Sevkli, and G. Gencyilmaz, A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research, vol. 177, no. 3, pp. 1930–1947, 2007.
- Y. B. CANBOLAT, E. GUNDOGAR. Fuzzy priority rule for job shop scheduling. Journal of intelligent manufacturing, 2004, vol. 15, no. 4, pp. 527–533.