3
$\begingroup$

I'm a software developer who likes to play a video game that has a complex economy. I realized that the type of problem I'm trying to solve mimics real life operations research problems, and I am seeking your assistance in designing an OR-Tools model that would solve a scheduling problem given several constraints. I'm new to OR-Tools and finding some difficulties with describing my problem in the form of constraint programming. I already have python code that can unravel the requirements into phases of production naively based off of the total raw materials required for each component.

I've answered the following questions:

What is the known information in this problem?

There are five planets with mining and production machines.

It takes roughly 3 minutes to travel from planet to planet.

Each mining machine can do 2 jobs, each production machine can do 5 jobs.

The maximum amount each job can do is 100 units.

Mining machines are used to extract raw resources. Production machines are used to make 1. components to producible items 2. producible items themselves. Sometimes producible items also require a combination of raw materials and producible items.

It takes about 1 minute to travel between mining and production terminals on the same planet.

These five planets have overlapping but different sets of resources on each.

For example, Planet A has "chemicals", "biomass", "copper" and Planet B has "carbon", "chemicals", "biomass".

There are many, many items. Here is an example: A first aid kit requires 1 bioplasma and 1 textiles. A unit of bioplasma takes 3 biomass. A textile requires 2 biomass (not bioplasma) and 1 refined chemical. 1 refined chemical takes 3 chemicals. We will want to combine different orders that will share raw materials and intermediate items.

In order to mine 100 raw materials, it generally takes about 23 minutes. It takes about 14 seconds to mine one raw material. In order to produce items, it varies depending on the number of raw materials that go into each item. This isn't public information but can be reverse engineered. I can determine this formula later as needed.

We do know what each producible item requires and all the raw materials and their locations. This has been entered into a large spreadsheet built as an adjacency matrix.

Technically, each planet has a player's storage with a capacity that can be expanded for money, transferring items between planets costs money, and traveling between planets also costs money. Profitability isn't really a concern however, because it's a given that fulfilling the order will be profitable. Our real goal is to have a fast turnaround time.

What are the decision variables or unknowns in this problem?

We don't know how much of each producible item an order will request until the request is made. We don't know what combination of producible items will be requested until the request is made. Which jobs should occupy each slot? How much of each item in the job should we do? What order should we do these operations?

What are the constraints on these variables?

Each planet has a set of mining machines and production machines. Each mining machine can only do 2 jobs. Each production machine (including intermediate items) can do 5 jobs at once. It takes 3 minutes to transition between planets. It takes about 1 minute to travel between mining and production terminals on the same planet. You can't collect output of the jobs early. They must complete and can't be interrupted once started.

What is the objective?

The objective is to produce a schedule of mining/production operations that minimizes our time spent in the game. Essentially, a production plan and schedule.

What am I asking you for?

I'd like your sagely advice on how to describe this problem in the form of constraint programming/scheduling/production planning. The output would be a list of operations needed to fulfill an order of products.

Some Examples

Let's say we wanted to fulfill an order of 100 first aid kits.

This would require 100 bioplasma and 100 textiles.

100 bioplasma would require 300 biomass.

100 textiles would require 200 biomass and 100 refined chemicals.

100 refined chemicals would require 300 chemicals.

In total, 500 biomass and 300 chemicals are required in raw materials.

A naive answer might look like:

  1. Go to Planet A and start 2 jobs of mining biomass, for a total of 200.

  2. Then go to Planet B and start 2 jobs of mining 100 chemicals. 23 minutes elapse, and the player would mine 100 more chemicals and 100 more biomass on Planet B.

  3. Go back to Planet A and start another 2 jobs of mining 100 biomass each.

  4. After transferring all the raw materials back to one of the Planets, let's say Planet A, the player could then start 3 jobs of refining ~33 bioplasma (consuming 300 biomass) and then start 2 jobs of refining 50 refined chemicals (consuming 300 chemicals).

  5. After about 34 minutes elapse, they start 5 jobs of refining 20 textiles, taking about 23 minutes.

  6. Finally, they start 5 jobs of producing 20 first aid kits each, for a total of 100 first aid kits. As you can see, the jobs can be split up across the "slots" to speed up the process.

$\endgroup$
2
  • $\begingroup$ what is the name of the game? $\endgroup$ – user3680510 Feb 19 at 13:47
  • $\begingroup$ @user3680510 I'd rather not say $\endgroup$ – 0x1F602 Mar 10 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.