Dealing with Optimization Problems: FitJSP — Fancy Interactive Tool for Job-Scheduling problems.

Introduction

In this post, we are going to discuss about one of the well known problems in computer science, Job-Shop Scheduling. The researchers have done a vast amount of studies in finding a fast and an efficient solution, but still it remains one of the most challenging task nowadays.

Job-shop scheduling is an optimization problem and operations search in which jobs or tasks are assigned to resources at particular times. In other words, finding the optimal strategy to distribute multiple tasks/jobs over several available machines. But how this problem is tackled? Well, nature has always been a great inspiration for mankind. Have you ever wondering how the tasks are been allocated in bee colony? What about ant colony? How can they find the fastest route from anthill to food place in order to reduce time and increase quantity (efficiency)? When an ant colony is confronted with the choice of reaching their food via different routes, the choice at the beginning is random. Ants use pheromone-based communications, by laying down pheromone trails in the paths they walked through. In this way, if other ants find such a path with pheromones, they do not travel more randomly but they start to follow these paths. Pheromones can evaporate, thus resulting in reducing its attractive strength. Therefore, the route with a bigger pheromone density, meaning that a lot of ants chose this route, appears to be the shortest path in the space of routes.

The sample explained above is one of the approaches for this kind of problems. Other nature-inspired algorithms include artificial neural networks (inspired by neural system at humans), bees algorithms (population search algorithm), genetic algorithm (inspired by the process of natural selection that belongs to larger class of evolutionary algorithms) and many others.

*Example of Job scheduling problems [6].*

Constraints for the Job-Shop Problem

There are different constraints for the job problems which depends on the problem specification and requirements. However, these are the main constraints generally defined:

A machine can only be assigned one task at a time.
A job or task, once started, it must run to completion and interruptions are not allowed.
No task for a job can be started until the previous task for that job is completed.
Machine dependency and capacity constraints.

Factors to describe Job-Shop Scheduling Problem

Arrival pattern
Number of machines(work stations)
Work Sequence
Performance evaluation criterion

Our problem

Our problem consists of n products to be produced in different machines. There are 2 sequence of actions to be considered, the preparation and the drying process. First, the product should be prepared in production machines where all the ingredients are merged to form the products in a specific time period, followed by drying process where products stay for a longer time to solidify. Each product spends a defined time in each process, and each machine involves capacity constraints. The schedule is done in weekly basis. The goal in this problem is to schedule the production of such products in an efficient way and minimizing the makespan. The makespan is the total time elapsed in that schedule (that is, when all the jobs have finished processing). We have used genetic algorithm to tackle this problem. Moreover, we have also developed a drag-and-drop online tool where the user can interact in real time with the schedule recommended by the algorithm and can easily update it (see the demo video below). the performance criteria of our job scheduling algorithm are:

Makespan — total time to completely process all jobs.
Daily makespan — maximizing the scheduling daily in order to have some room left for emergency orders at the end of the week.
Utilization of machines and workers.
There should not occur conflicts in production and drying machines.

Genetic algorithm

Genetic algorithm is basically a heuristic method that is inspired by the natural selection to find the best solution to a problem. Usually, this algorithm is used when you do not have any information about the best case scenario, trying to find a better local optima. The algorithm has a well defined workflow, but the hardest part is how to transform or model the problem to be suitable for the usage of this algorithm. The process of a genetic algorithms are as follows:

To begin with, the workflow of genetic algorithm start with an initial population. the populations is initialized by satisfying machine constraints and allocating products by randomly choosing the timeslots and machines. Coupled with initial population is fitness function, which calculates the performance criteria score with satisfying the constraints. Fitness function is considered as a selection process, assigning a score for each individual to indicate whether this individual is a strong or weak one. In the strong individuals, 2 random parents (individuals) are selected which will lead new individuals in the population. This process is named as cross-over and mutate functions.

Cross-over and Mutate functions

In this step, 2 new children are created who are better than its parents. The logic applied in our solution is that the first child takes the best rows from each parent where best means minimum number of collisions based on constraints. The second child takes the best machine selection with the minimal number of collisions within the interval. Therefore, by combining these two approaches, we hope to create a better individual.

On the other hand, mutate functions in a stochastic way to shuffle the timeslots and machines for each individual. The key idea of this function is to help children by thinking different and explore other paths differently than other individuals. Of course, that different path can also lead to a dead end, but can also bring to a better solution. After mutating the child, a new population is formed and the whole process re-iterates. This process is stopped when the desired performance score is reached or based on a threshold number of steps posing the best local optima.

Demohttps://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FHScU0w7ONa4%3Ffeature%3Doembed&display_name=YouTube&url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DHScU0w7ONa4&image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FHScU0w7ONa4%2Fhqdefault.jpg&key=a19fcc184b9711e1b4764040d3dc5c07&type=text%2Fhtml&schema=youtubeDemo video of our drag-and-drop online tool.

This video shows a simple demo about our drag-and-drop online tool. The user can apply a set of actions like update, move, create new event, delete or resize the events. First, to start the application you should click on try demo to execute the algorithm. Second, the algorithm suggests a schedule applying the logic explained above. Then the user can start the interaction to modify the recommended schedule. While playing with the events, the tool is extended with notification panel to inform in real time the user whether this update has conflicts or not. Something that you might ask is that why drying process starts before production process ends (like product 0)? Actually, the drying process starts immediately after production process ends, but because timeslots are divided in 30 minutes, it is not that obvious. However, the blue bar above the event displays the start and end points in time of the event.

Conclusion

In conclusion, our algorithm is pretty effective on tackling this problem. It is worth noting that the algorithm not only ends when it exceeds the number of steps, but also when it does not notice an improvements in the result after a specific number of steps. However, still a lot of effort is needed to improve and make it robust over different parameters and changes. The drag-and-drop tool built on top of genetic algorithm is very intuitive and a great feature for not technical users who are willing to use the output of the algorithm. At the moment it offers only basic functionalities and there is a lot of room for improvement.

Cheers ….

-Ali Doku