I have to solve a problem in the field of operations research. I want to gather some general approaches to evaluate them to pick the most promising to design a problem-related program.

Problem definition

Company ACME that sells customized collages and has a production that adheres to mass customization principles.


  • A desk D where the collages are created (maybe there will be more desks in future, but not for now)

  • A collage C is composed of...

  • Diverse square pictures P

We can consider the collage as created, when the last needed square picture is created.

  • Marker M of color T and capacity c_m

A picture is drawn with one or more marker(s) of same color. Each picture consumes a certain amount of marker capacity. It is possible that a pictures can consume more than one marker. Empty markers can be refilled but that takes a fixed amount of time.

The drawer is an android that works 24/7 (since androids have no human rights yet) and can hold mutliple markers (there is a limit, we can assume 2 for now), if one marker is empty, he can switch to the next and doesn't loose time because of refilling. Changing the marker because another color is needed, also takes time.

The markers are not at the android's desk, only the one he currently uses. They get there at the time they're scheduled.

The problem now is to schedule the specific square picture assignments, the according marker assignments, marker refills and color switches so that every single step of the collage production is planned considering a high output rate (that includes the minimaziton of color switches).


I need help finding algorithms and ideas for solving the problem. Maybe there are some best practices or problem instances to map I haven't thought of. E. g. TSP, where I'm not sure how to apply it in this special case.

My Solutions/Ideas so far

  • Simulated Annealing The square Pictures assignments, marker assignments, etc. are consindered as events. Find a permutation of events that minimizes global cost function.
  • Auction class algorithms Every square picture assignment gets a balance of money according to the return value of a per-assignment cost function. The assignments can buy the needed resources in an auction house. Upon a valid buy, the resource and the assignment are scheduled.
  • Map to graph instance (Don't know exactly how to do that yet) and find path with minimum weight.

Additional info

There is a meta tier with a superior ERP (Enterprise resource planning) system, that already does some rough planing. The task here is the detailed planing as a MES (Manufacturing Execution System) would do it. But I don't know the number of collages I have to plan in a given time frame. I just know that it is an ongoing problem, and that there is no need to use an online algorithm. The program I'll intend to develop gets called on demand to schedule the production for some days.

I found a way to map the problem to simulated annealing and another approach following the auction class algorithms. I need help with evaluating these approaches, or even collecting new ideas, best practises to solve this problem, since I never dealt with a problem instance like this before. E. g. an answer like take a look at algorithm xyz would help me out, or first approaches to a graph mapping.

  • It looks as if you forgot to state an actual question. – Martijn Pieters Jun 17 '13 at 15:47
  • I thought that was clear, I want to solve the described problem. But I'll add a question. Thx for your hint – mike Jun 17 '13 at 15:50
  • You seem to be forgetting that another limit is how many markers can an android hold? Otherwise, an android could hold every marker required to do the collage/do every collage for the day/do every collage for the year/etc. – Neil Jun 17 '13 at 15:51
  • I'll add that too. One per arm for now. – mike Jun 17 '13 at 15:56
  • 1
    @mike I think the problem is clear, but our question is, what do you need help with? It sounds like a homework problem which we can help with, but generally we like to see that the OP at least attempted a solution or demonstrated what they have tried. I don't see what specifically you have tried to solve this problem. – maple_shaft Jun 17 '13 at 22:35

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.