Arranging tasks with specific constraints (scheduling)

Question

I have the following problem:

Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example:

Suppose we are scheduling talks in a conferece. Each talk has a duration, and we can use as many rooms as we need. For each room, we have two sessions: one in the morning, and one in the afternoon. Morning one starts at, say, 9 AM and must end exactly by noon. The afternoon one starts at 1 PM and must end between 4PM and 5PM.

How do i arrange these talks in sessions in such a way that uses the least amount of rooms possible?

I've researched some scheduling problems, but none of them seem to take into account the constraints i need. I have read about:

http://en.wikipedia.org/wiki/Interval_scheduling

http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling

http://en.wikipedia.org/wiki/Flow_shop_scheduling

Answer 1

This is actually a bin packing problem, rather than a scheduling problem. If I remember correctly (it's been a long time) bin packing is the dual of scheduling.

In the most basic kind of bin packing problems each room would be available for exactly three hours, and the goal would be to minimize the total number of three-hour sessions you would consume. Your problem has an extra constraint that rooms come in pairs that are available for 3 and 4 hours.

Bin packing problems are usually NP-complete, but there are some heuristics that tend to work well in practice. For the basic bin packing problem the usual heuristic would be to sort the talks from longest to shortest. Then start placing talks into rooms in that order. For each talk examine the rooms in the same order. Place the talk in the first room where it will fit. You only rent a new room if you have a talk that won't fit in any of the existing rooms.

There's a bit more on the Wikipedia Bin packing page: http://en.wikipedia.org/wiki/Bin_packing_problem

And I found this article, which describes some of the approximation algorithm results in this area (as of 1987): http://www.columbia.edu/~cs2035/courses/ieor6400.F07/hs.pdf