Scheduling problem

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
Posts: 4
Joined: Wed Mar 12, 2014 4:36 pm

Scheduling problem

Post by monkey68pl »


First of all - I'm sorry for long description of problem. I tried to find some suggestions how to tackle this, but nothing really convinces me, and I decided to post my question here.

Problem - how to schedule production on assembly line.

Overview - assembly line can make 3 different products (P1, P2, P3), each made on specific tool (T1, T2, T3). Tools are prepared for production, then assembly line changes tools and starts production of specific part. Example: Currently line is producing P1, tool T2 is prepared, line finishes P1, changes tools, starts P2. Each part has minimum amount of parts which have to be in stock (which defines production start point), each tool has different preparation time (which defines length of production of previous part - in example above P1 production time has to be longer than T2 preparation time), each time when tool is changed is wasted (line not producing), total stock cannot be higher than predetermined level.

There are several other factors which state how good particular schedule is, but it's way too much to talk about all of them.

Question - how to (practically) create optimal schedule, given a) future part consumption, b) all parameters required, c) scoring associated with each aspect mentioned above.

My initial thoughts were to create genetic algorithm to solve this, with two possibilites:
1. Several steps - first round to find optimal schedule with fixed production time, second round to optimize production time, third to optimize tool changing time, etc. - I get the impression that this would not produce optimal result
2. One step, optimizing all aspects at once - this will require massive starting population, as almost all results will be discarded in first generation (not fulfilling production demand)

Two risks which I see for now is high complexity of practical usage (with real number of products/tools) and complete lack of knowledge about fitness landscape.

Any hints where I should look for ideas?

Best regards,

Posts: 1
Joined: Sat Feb 22, 2020 11:12 pm

Re: Scheduling problem

Post by hassanitoyay »

I happen to have worked in a company where they needed to optimize the scheduling of specific tasks to different employees and If I remember correctly it was an operations research and optimization problem. It is also an NP-hard problem so yes the solution will be very complex and time consuming. I'm not sure what type of problem exactly this is called (maybe Job shop or flow shop) but I suggest you pick up " Scheduling: Theory, Algorithms, and Systems By Michael L.Pinedo" (you can find it online) and read the first few chapters that tell you exactly under which category your problem falls. And then you can find the general solution in the chapter about that category.
I hope I helped put you on the right track.
Post Reply