Is there any planning algorithm that allows scheduling n-sets of events?

Question

The problem is a kind of scheduling problem, I would like to identify what kind of problem this is or, at least, what kind of problems it relates to?

Let's say we have n sets of events S1,S2,...,Sn, where an event has the duration of one day.
Each event set has only one repetition per week.
Each event set has an event repeating period, may be once a week, every two weeks, once a month, etc...
I need to re-schedule the sets of events in order to optimize the planning.
The algorithm output is a re-schedule of events that optimize events occurrences of each set in order to get the minimum number of distinct events between the event sets, virtually the result should be an event set with the smallest possible events number.

First example

Suppose to have to event sets S1 and S2, S1 repeats once a week, S2 repeats every two weeks.

 W1 W2 W3 W4 W5 ... WSK
S1. x x x x x 
S2. x x x

The resulting scheduling is a that the events in the same week of each sets must be set to the same day

Second example

Suppose to have to event sets S1 and S2, S1 repeats every two weeks, S2 repeats every three weeks.

 W1 W2 W3 W4 W5 ... WSK
S1. x x x 
S2. x x 

Week 1 can be merged. But How can I manage W3,W4,W5?
Does S2 in Week 4, has to be merged with S1 in Week 3 or in Week 5?
What kind of rule can be defined to check if merging is possibile? Should I define a interval of days where an event can be moved? I think something is missing in the problem definition.

Third example

Suppose to have more than two event sets

 W1 W2 W3 W4 W5 ... WSK
S1. x x x x x 
S2. x x
S3. x x 

What kind of rule should I apply?

Is there any general algorithm?

• marstato: I dont understand your question. The title says without collision and your example says must be set at the same time. Please clarify.
• landal79: @marstato, I changed the title, events of each set which are 'near' (to define the meaning of near), should be set at the same time
• marstato: Just to make sure i understand correctly: in weeks where only one schedule has an occurence the start- and stop times of that occurence are irrelevant. In weeks where mutliple schedules have occurences all of the occurences must start and end at the very same time. Is that correct?
• landal79: I edited the question, to simplify we can assume an event is one day event
• marstato: So in weeks where mutliple schedules have an event these should be on the same day?

Answer 1

Lets abstract your question a bit further: Lets not talk about weeks but rather about timeslots.

I'd take this straightforward approach:

When planning K timeslots into the future, create a 2-dimensional data structure in memory, like so:

 TS1 TS2 TS3 TS4 TS5 ... TSK
Sch1.
Sch2.
Sch3.
 ...

Then fill the cells in this structure with the scheduled events:

 TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8 TS9 TS10
Sch1. X X X X X 
Sch2. X X X X
Sch3. X X X

You can now expriment with that. Define a near-factor N. Whenever there is more than one event within N timeslots, group them to the earliest (or latest - does not really matter) timeslot.

Pseudo-Code:
for (index from 0 .. K)
 eventsInNTimeSlots = // find all the events in the current + N - 1 timeslots
 if (eventsInNTimeSlots.size > 1)
 for (event in eventsInNTimeSlots)
 event.timeSlot = index

You can then write a piece of code that tries a bunch of different N, even:

rawSchedule = // as defined above
results: Map<Number,Number> // maps N to the number of days with events
for (N in 0..5) {
 schedule = copy rawSchedule
 // optimize schedule as defined above
 nEvents = // count days with events in schedule
 results.put(N, nEvents)
}
// find the minimum value in results and use the associated N

---

If you need to plan ahead for ever (until eternity), you can use the same algorithm: calculate the number of timeslots after which your schedule starts to repeat. If your schedules are all as simple as every X days you can simplay calculate lcm(X0 ... Xi)

Use that number as K

• landal79: how can I choose the near-factor? About event grouping, what if I have constraints on numeber of days I can move an event? i.e. I can't move an event to early
• marstato: These restrict the near-factor. If you cannot move an event by more than 4 timeslots, 4 is the upper limit. This algorithm will not find a perfect solution, more likely only a viable one.
• landal79: Do you think that this kind of problem has a name in computer science literature?
• marstato: Probably, but i dont know it :/