Hi,
Currently, I have a difficulties in scheduling tasks which duration is dependent on previous tasks . For example, I have the following two sets of tasks to complete on two different machines M1 and M2:
S1: T1 -> T2 -> T3
S2: T4 -> T5
Each task has duration of 2s. However, If I perform T5 immediately after T1 on the same machine, the duration of T5 can be shorten into 1s. Furthermore, If I perform T3 after T5, the duration of T3 can be shorten into 1s as well.
Therefore, the schedule below has a time span of 4, not 6.
M1: T1 -> T5 -> T3
M2: T4 -> T2
My question is: how do I model this type of "duration dependency" in my CSP model? Or which keywords I should use to search for related information?
Hi Mario
Could you explain why processing T5 after T1 shortens its duration, and the same for T2?
It would seem to me this can be modeled very similarly to a model with part (previous) dependent set up times. Let the processing time be the smallest potential processing time and then let the difference be handled by the setup time
is the 2 machines have the same power and type?
it seems that executing T2 on M2 reduce the time and the same for T5 on M1
Hi all,
>> Could you explain why processing T5 after T1 shortens its duration, and the same for T2?
You can assume both T1 and T5 needs a similar set-up procedure, so if T5 is processed before T1, time can be saved.
>> is the 2 machines have the same power and type?
Yes, you can assume that.
Hi Ka Lun, Mario Leung,
This particular problem can be solved using scheduling with set up times as pointed out Thomas K. Keyser. The reference is survey of Allahverdi, Ng, Cheng, Kovalyov.
These type of problems are also called scheduling problems with learning effect when the processing of task is decreased in time when you process similar tasks.
My advise is to establish the complexity status of the problem, may be it is known that it is NP-hard.
With respect,
Maksim
Hi Mario,
My two cents:
1) I guess that the change over time is the influencing factor and since it is 2 seconds max in your case, it gives an impression that it is the task time.
2) At a bigger magnitude your case seems similar to sequence scheduling in paint shops. Overall time is optimized in a specific sequence of colours - a sequence dependent set up time optimization problem.
3) The following papers may give you some lead:
a) A sequential ordering problem in automotive paint shops - this is available in researchgate and you have to request for full text from the authors.
b) Scheduling algorithms by David Karger (MIT), Cliff Stein, Dartmouth college, Joel Wein , Polytechnic University. You can get the full text in google search itself.
Happy if it helps. Good Luck !
Regards,
Guru
Hi Gururaman, Mario,
My advise is regarding the general method of dealing with the problem and its qualities not about particulars. Sure, it is very important to be accurate while dealing with details and the advise of Gururaman regarding particular methods is of use.
I further appologize that I may have caused discomfort Mario, since the question is regarding the keywords of interest not the general methods of the solution.
With respect,
Maksim
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms