Chellenging Schedule Pre-empting Query...impossible?

[bmiller3419]

I have a schedule of recurring "programs" that I would like to create a list from a database. The programs need to be placed into multiple time-slots (by weekday) and repeat every week. The database has two tables:
tblProgram lists the program title and program type. It is connected via one-many relationship to tblSchedule. tblSchedule lists has multiple records for each program listing the day of the week, start and end time the program occurs.

Here is the database structure (abridged):
tblProgram
- programid
- programtitle
- programtype: recurring or onetime
- startdate: date to start program repeat
- recurringenddate: program repeat expires

tblSchedule
- scheduleid
- programid
- weekday
- starttime
- endtime

Here is some sample data for "program1":
tblProgram:
programid title startdate enddate programtype
1 Program1 1/1/2004 1/1/2005 recurring

tblSchedule:
programid scheduleid weekday starttime endtime
1 7 2 1:00 PM 2:00 PM
1 8 3 1:00 PM 2:00 PM
1 9 4 1:00 PM 2:00 PM
1 10 5 1:00 PM 2:00 PM
1 11 6 1:00 PM 2:00 PM

Note: the start and the end date are for making programs effective or expired, it is not necessarily the first day the program appears.

Putting a query together that lists the program title along with all the times for a certain weekday is simple.

SELECT programtitle, weekday, starttime, endtime FROM tblProgram INNER JOIN tblSchedule ON tblProgram.programid = tblSchedule.programid ORDER BY starttime;

Here is some sample data for Thursday (5):
title weekday starttime end time
Program1 5 9:00 AM 10:00 AM
Program2 5 10:00 AM 11:00 AM
Program3 5 11:00 AM 1:00 PM
Program4 5 1:00 PM 2:00 PM
Program5 5 2:00 PM 3:00 PM
Program6 5 3:00 PM 4:00 PM

Here is the challenge!
There is "Progam Special" that needs to be added to the database. It's start and end times overlap other programs. It's a one-time, non-recurring program that needs to "pre-empt" any other recurring programs. For exmaple, Program 4 starts at 1:00 and ends at 2:00, Program 5 starts at 2:00 and ends at 3:00. "Program Special" occurs once on a certain week, starts at 1:30 and ends at 2:30.

Here is "ProgramSpecial"s data:
tblProgram:
programid title startdate enddate programtype
7 ProgramSpecial 10/28/04 10/28/04 one-time

tblSchedule:
programid scheduleid weekday starttime endtime
7 80 5 1:30 PM 2:30 PM

How do I create a query that inserts "Program Special" into the list?
title weekday starttime end time
Program1 5 9:00 AM 10:00 AM
Program2 5 10:00 AM 11:00 AM
Program3 5 11:00 AM 1:00 PM
Program4 5 1:00 PM 1:30 PM
ProgramSpecial 5 1:30 PM 2:30 PM
Program5 5 2:30 PM 3:00 PM
Program6 5 3:00 PM 4:00 PM

 

[aleb]

Hello bmiller
You can use Union select query
Syntax for union select is following:

Select yourfield
From yourtable
where(((yourcritirea))
Union select your field
From yourtable
(((yourcritirea));

Here is live example:

SELECT distinct Table1.Field1
FROM Table1
WHERE (((Mid([field1],1,2)) Not In ("Ae","Be","Fe","Ge","He","Me","Pe","Te","Ve","Xe","Ze","Au","Bu","Fu","Gu","Hu","Mu","Pu","Tu","Vu ","Xu","Zu","6e","6u","8E","8U") And (Mid([field1],1,2)) Not Like ("c*")))
UNION select distinct Table1.Field1
FROM Table1
WHERE (((Mid([field1],2,1) & Mid([field1],6,2)) In ("ep9","up9")))
ORDER BY 1;

 

[bmiller3419]

How would that work?

I'm not quite sure how that would work for my example. I can already return a list of all the programs for a certain weekday, including recurring and special programs that pre-empt.

This query:
SELECT programtitle, weekday, starttime, endtime FROM tblProgram INNER JOIN tblSchedule ON tblProgram.programid = tblSchedule.programid ORDER BY starttime;

with the special program in the database, will return a list of all the programs:
title weekday starttime end timeProgram1 5 9:00 AM 10:00 AM
Program2 5 10:00 AM 11:00 AM
Program3 5 11:00 AM 1:00 PM
Program4 5 1:00 PM 2:00 PM
ProgramSpecial 5 1:30 PM 2:30 PM
Program5 5 2:00 PM 3:00 PM
Program6 5 3:00 PM 4:00 PM

I'm trying to get it to shorten the end time of Program 4 and delay the start time of Program 5 if ProgramSpecial is scheduled for 1:30-2:30. So that it ends up looking like my last example:
title weekday starttime end time
Program1 5 9:00 AM 10:00 AM
Program2 5 10:00 AM 11:00 AM
Program3 5 11:00 AM 1:00 PM
Program4 5 1:00 PM 1:30 PM
ProgramSpecial 5 1:30 PM 2:30 PM
Program5 5 2:30 PM 3:00 PM
Program6 5 3:00 PM 4:00 PM

 

[The_Doc_Man]

From your exchange with aleb, I gather that, in queueing theory terms, this is a one-processor schedule. I.e. single-stream operation, only do one thing at a time, no way to load-balance with another job stream.

Please confirm that before I go off the deep end with a discussion that will get awfully hairy awfully quick.

 

[bmiller3419]

Clarification

Yes, only one program event can happen at a particular time.
The challenge is adding special one-time events that change the schedule of recurring events. One-timers can start and/or end at the same time as a recurring event, and/or they can start and/or end in the middle of a recurring event.

Just a little background, I'm planning this to go into an Access or SQL database. The report will be a ASP or .NET webpage. My report goals are to be able to figure out:
1. When the programs for the day start and end (including specials)
2. What program is happening at any particular time (including specials that may pre-empt)

Although I'm fearful of where this discussion will go, Thanks in advance for anyone's responses

 

[The_Doc_Man]

The general approach for this in classical queueing theory is to add a "priority" field to the scheduler. Your "special" jobs get higher priority. You need not less than two possible priorities. If your managers are anything like mine, the two priorities are

1. Ultra-super-urgent
2. More important even than #1.

Seriously, with at least two priorities, the problem is soluble. With more than two priorities, you can confuse yourself badly. So be careful about how many priorities you define. To FORCE yourself to keep it simple, define your priorities with a Yes/No field: Special, yes or no, and then sort this in DESCENDING order ('case NO maps to 0, Yes maps to -1, which is LOWER than 0 if you just sort without specifying DESCENDING order).

The algorithm is done in two parts. First, create a query to identify jobs sorted by

a) the earliest start time
b) the highest priority

Then it is a matter of determining whether a job's (start time + processing time) overlaps the next job, which USUALLY requires some VBA code to do this.

Finally, you just populate the schedule based on the results of the query as the basis for job order and the VBA code as the basis for start/stop times.

I'll toss in a couple of other issues.

When you have a schedule where you have a tie in start-time AND a tie in priority, break the tie using shortest processing time, which is also a required field. (If you didn't have processing time, you couldn't estimate the start of the next job, right?) SPT-scheduling can be proven using methods of formal queueing theory to maximize job throughput. I.e. SPT means you finish the most jobs in the fastest time. So it ain't a bad thing to apply.

NOW, there comes a question you have to resolve for yourself 'cause this depends on your business rules.

SUPPOSE you have a special at 1 AM lasting 1 hour, a regular job starting at 1 AM lasting an hour, and a regular job starting at 2 AM.

The special job drop-kicks the regular 1 AM job. So when 2 AM rolls around, which job do you start next? You can preserve submission order or, if the jobs are different in length, you can apply SPT order. If the job has one more requirement, like "Must Be Finished By" time, you could use THAT as a tie-breaker, picking the earliest "drop-dead" time first among priority equals that overlap potential start times.

This is an example of Minimized Late Time (MLT) scheduling. If you are chewed out for how late some jobs run, this minimizes the chewing-out time. It is another option (like SPT scheduling) derived from queueing theory.