Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Containment-only Interval Standard



On Thu, Aug 4, 2011 at 7:35 AM, Hossam A. H. Fahmy
<hfahmy@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
> Dear 1788 members,
>
> 2011/8/4 Lee Winter <lee.j.i.winter@xxxxxxxxx>
>>
>> On Wed, Aug 3, 2011 at 2:56 PM, Michel Hack <hack@xxxxxxxxxxxxxx> wrote:
>>
>> > (1)  Intervals as imprecise single values.
>> >
>> > (2)  Intervals as bounded (or semibounded) ranges of separate values.
>>
>> Is there a description or definition available for the concept
>> "separate values"?
>>
>
> I do not have an exact definition of "separate values" nor of the second
> type mentioned by Michel, but I have a simple example to present where both
> types may be used:
>
> The potential start and end times of tasks in a project management program
> or a real time embedded system might be represented as intervals. For
> example a task may be started any time within [t1, t2] or start any time
> after t1 which is represented as [t1, infinity]. These intervals belong to
> the second type described by Michel which are ranges, possibly very wide
> ranges, and not an imprecise value.

I disagree.  The above-described intervals do not specify collections
of values all of which are "active".  Instead they represent a single
value, the start time, which must lie within the intervals of
"potential" or "allowable" start times.  The intervals are simply
constraints on the a single value.

The statement that the above-described intervals are not imprecise
values appears to me to be false.  The _actual_ start time will
definitely be a single, specific value limited by the precision of the
clock measuring that time.  And the representation of that start time
value would be representable in a narrow interval whose width
represents the precision of that clock.  The _potential_ start times
represented by the above-described intervals  could be interpreted as
simultaneously active possibilities, but in most scheduling cases the
more useful interpretation is exactly that of an imprecise description
of the desired start time, thus just a constraint.  So the best that
could be said about the above example is that it illustrates two sides
of the same coin, for which the two possible interpretations are not
in conflict and so do not require special processing.

It appears to me that many interval algorithms have a distinctly
different flavor in that all of the values enclosed by the interval
are independently "active" in the sense that they simultaneously
coexist.  Operation of the algorithm often divides such composite
intervals into sub-intervals until there is either zero or one
"active" value within each of the resulting intervals.  Thus, in a
sense, those interval algorithms reduce the starting intervals of
simultaneous character (Michael's type two) down to a possibly-empty
collection of non-simultaneous intervals (Michael's type one).

> A task with duration d that must start
> within [t1,t2] and end within [t3,t4] will require us to solve
>
>  [t1+d,t2+d] intersect [t3, t4]
>
> to find the possible starting and ending dates for this specific task.
>
> Now if the duration of the task is not precisely known (first type described
> by Michel) but is given as [d-delta, d+delta] then we have the two types
> mixed together in one application.
>
> Michel has made this point several times and I agree with him that the two
> types are different and may require us to think differently.

The above statement is opaque to me.  What differences in thinking are
involved in the two types of intervals?  I ask this because only when
there is conflict between the two interpretations is there any impact
on the standard.  When does the difference in thinking (meaning
perspective or interpretation) require a difference in processing?

Lee Winter
NP Engineering
Nashua, New Hampshire
United States of America