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.
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.
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.