Description
The Problem
The goal of GRASS is to utilize the Carbon Aware SDK to reduce the carbon intensity of all of manufacturing, this includes everything from the furniture produced in a small local wood workshop to the buildings erected by multinational construction companies and so much more.
Scheduling the various tasks that go into producing a chair or erecting a house is a monumental problem. Especially, when it is just one of many orders that must be processed simultaneously and with only a limited amount of resources available. Such resources are for instance tools like a table saw or a cement mixer, which cannot be used to work on two different tasks at the same time.
The name for this genre of problems is "Job-Shop-Problem". Unfortunately, most Job-Shop-Problems with applications in the real world, like the Flexible-Job-Shop-Problems are NP-complete, which means finding the optimal solution computationally is extremely difficult and extraordinarily time consuming. Therefore, these problems have been tackled by many scientists and researchers trying to find strategies and algorithms for finding close to optimal solutions. Where, in the past "optimal" was commonly defined as the minimal time of completion of all tasks. However, Job-Shop-Problems can be optimized on a number of metrics, and I am hereby proposing to optimize for carbon intensity. While others have proposed approaches that optimize the overall energy consumption, my literature review concluded that to the best of my knowledge I am the first to propose carbon intensity as a metric for optimization.
The solution
There are several strategies to finding a close to optimal solution. One of the most popular approaches is using a genetic algorithm, which drastically cut down the number of solutions that need to be tested, thus reducing computation time, while still reliably finding close to optimal solutions.
The input to the genetic algorithm consists of a set of machines and as set of jobs. For each job an order list of tasks is provided. Each task is defined by a set of machine processing duration in minutes. If a task cannot be processed on a given machine the time value for that machine must be infinite. An example for this would be drilling a hole, which one would not want to do with a cement mixer, therefore the respected time must be infinite, whereas the same task would take a finite amount of time, when using a drill. Additionally for each machine the power required to run it must also be provided in Watts.
The genetic algorithm will then generate an initial population. A population is a set of possible schedules. A possible schedule is a schedule that completes all tasks of every job and respects the order constraint, which states that no task can start, run or finish before its predecessor task is completed. There are various methods of generating this initial population, finding the optimal method remains a topic for further research, so far only random job and task selection has been considered. After the initial population has generated a set of its offspring is generated by selecting two solutions for the population and combining some of their features, so that a new and different possible schedule is generated. Again, there are several strategies for generating offspring, we are using random selection so far, but finding an optimal strategy remains another topic for further research. Then, to introduce new features a set of possible schedules is selected and mutated. After a mutation a schedule mostly resembles the original schedule only with a few alterations. Here we also resort to random selection of alteration, while finding an optimal mutation strategy is another topic for further research.
Finally, all generated possible solutions are tested for their fitness. GRASS allows two options here. The first option is to focus only on the CO2 footprint of each schedule, this will return the schedule with the smallest CO2 footprint. The second option is to first select based on minimal completion time and use low the CO2 footprint as a secondary criterium. In general, it can be expected that schedules generated by the first option take longer to complete all tasks than the schedules generated by the second option, but they will also generally have a smaller CO2 footprint, than those generated by the second option. Fit enough solutions will form the base population of the next generation and thus the cycle begins anew. This is repeated until a max number of iterations is reached. The schedule with the smallest CO2 footprint within the final generation is chosen and present as the solution.
How does GRASS utilize the Carbon Aware SDK
The carbon aware SDK sits at the core of GRASS, because GRASS relies on the forecast feature of the Carbon Aware API to evaluate the fitness of a possible solution and to schedule tasks optimally in their given time frame.
Impact and Reach
The reach of my solution is very significant. GRASS is solving one of the fundamental problems of business administration, that sits at the heart of every manufacturing enterprise, while it might also be applied to problems outside of the manufacturing scope.
Its impact depends on the individual enterprise. Choosing to primarily optimize for the CO2 footprint will provide a bigger impact on greenhouse gas emissions than optimizing primarily for completion time and using the CO2 footprint as a secondary factor.
Feasibility and Vision for the future
Currently the forecast horizon of the Carbon Aware SDK is limiting the use-case of GRASS. However, I expect this to be upgraded in the future, even if accuracy will decrease the further a forecast reaches into the future. However, I am hopeful, because patterns like sunrise and sunset, winter and summer seasons are relatively easy to predict and therefore the impact of solar energy on the grid, as there will always be more solar energy at noon than at midnight. Therefore, collecting more data on the present will help build more sophisticated models that will help predict further into the future.
Once this is achieved, usage of my approach and other solutions like it will hopefully be widespread. Manufactures can then decide what they want to focus on either finishing production as fast as possible or producing with as little carbon intensity as possible. Customers can then reward companies that chose the latter by preferring their products for purchase.
However, until then is a long way, which I would like to use to research and refine my solution and its results. An integration into the Carbon Aware SDK and its API would be another major step and I'd be honored, if given the opportunity.