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?

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