1

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.

Production

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

Question

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.

mike
  • 153
  • 5
  • 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
  • Can you provide some sample input data? – Robert Harvey Jun 17 '13 at 16:55
  • Sry, Unfortunately I can't, because I don't have any. I'm even sure that I coulnd't, if I had, because it would be customer data. – mike Jun 17 '13 at 17:09
  • I think the question is a real one. I have a certain scheduling and allocation problem instance and I want best practises to solve it. Since I am not sure, and I doesn't want to end up with a bad concept. So could you please reopen it, or refer to a stackexchange site where such questions are answered? – mike Jun 17 '13 at 20:39
  • 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
  • @mike Thanks for the info... I added your comment to the answer and reopened it. Hopefully somebody can give you some input – maple_shaft Jun 17 '13 at 23:39
  • Homework style problems would fare better if the OP could provide more than just bare Wikipedia links. CiteSeerX and Google Scholar are the OP's friends. Production planning has been researched in hundreds of papers and books, and this homework assignment is simply a word substitution from one of the actual problems (e.g. in the auto industry and elsewhere). What is a quadratic picture, anyway? – Deer Hunter Jun 18 '13 at 02:50
  • Oh, what I meant was `square` picture... in german a square is called `Quadrat`. I'll fix it. – mike Jun 18 '13 at 12:10

0 Answers0