0

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?

7
  • I dont understand your question. The title says without collision and your example says must be set at the same time. Please clarify.
    – marstato
    Commented Apr 27, 2017 at 15:36
  • @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
    – landal79
    Commented Apr 27, 2017 at 15:39
  • 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?
    – marstato
    Commented Apr 27, 2017 at 15:45
  • I edited the question, to simplify we can assume an event is one day event
    – landal79
    Commented Apr 27, 2017 at 15:52
  • So in weeks where mutliple schedules have an event these should be on the same day?
    – marstato
    Commented Apr 27, 2017 at 15:53

1 Answer 1

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

4
  • 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
    – landal79
    Commented Apr 28, 2017 at 11:24
  • 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.
    – marstato
    Commented Apr 28, 2017 at 11:53
  • Do you think that this kind of problem has a name in computer science literature?
    – landal79
    Commented May 4, 2017 at 7:19
  • Probably, but i dont know it :/
    – marstato
    Commented May 4, 2017 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.