greedy method

[santosh]

Hello all
I want to know whether there is any greedy approach for job sequencing
with variable job completion times..
if there is no greedy approach how to prove it...

[Alf P. Steinbach]

Re: greedy method

* santosh:[color=blue]
>[/color]

OT.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[David Kastrup]

Re: greedy method

"santosh" <santoshvarma@g mail.com> writes:
[color=blue]
> Hello all
> I want to know whether there is any greedy approach for job sequencing
> with variable job completion times..
> if there is no greedy approach how to prove it...[/color]

Well, one of the best batch scheduling strategies with regard to
several criteria is "shortest remaining processing time first".
Operating systems don't use it much in practice since few jobs
volunteer the information in advance.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum

[Alf P. Steinbach]

Re: greedy method

* David Kastrup:[color=blue]
>[/color]

OT in _four_ of the five groups posted to.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Ioannis Vranos]

Re: greedy method

santosh wrote:
[color=blue]
> Hello all
> I want to know whether there is any greedy approach for job sequencing
> with variable job completion times..
> if there is no greedy approach how to prove it...[/color]


Perhaps you are looking for PERT diagrams?

http://aisweb.wustl.edu/hr/empld.nsf/pages/pert

http://www.netmba.com/operations/project/pert/

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Ioannis Vranos]

Re: greedy method

Ioannis Vranos wrote:
[color=blue]
> There are also GANT diagrams which involve graphic bars.[/color]

GANTT

http://aisweb.wustl.edu/hr/empld.nsf/23e5e39594c064ee852564ae004fa010/74dc34f588656cf286256f3900692f0f?OpenDocument

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Ioannis Vranos]

Re: greedy method

Ioannis Vranos wrote:
[color=blue]
> Perhaps you are looking for PERT diagrams?
>
> http://aisweb.wustl.edu/hr/empld.nsf/pages/pert
>
> http://www.netmba.com/operations/project/pert/[/color]


There are also GANT diagrams which involve graphic bars.




--
Ioannis Vranos

http://www23.brinkster.com/noicys

[puzzlecracker]

Re: greedy method


David Kastrup wrote:[color=blue]
> "santosh" <santoshvarma@g mail.com> writes:
>[color=green]
> > Hello all
> > I want to know whether there is any greedy approach for job[/color][/color]
sequencing[color=blue][color=green]
> > with variable job completion times..
> > if there is no greedy approach how to prove it...[/color]
>
> Well, one of the best batch scheduling strategies with regard to
> several criteria is "shortest remaining processing time first".
> Operating systems don't use it much in practice since few jobs
> volunteer the information in advance.
>
> --
> David Kastrup, Kriemhildstr. 15, 44793 Bochum[/color]

just to add a little sparkling to it - "SORT BY FINISHING TIME and
eliminate overlaps"

[puzzlecracker]

Re: greedy method


David Kastrup wrote:[color=blue]
> "santosh" <santoshvarma@g mail.com> writes:
>[color=green]
> > Hello all
> > I want to know whether there is any greedy approach for job[/color][/color]
sequencing[color=blue][color=green]
> > with variable job completion times..
> > if there is no greedy approach how to prove it...[/color]
>
> Well, one of the best batch scheduling strategies with regard to
> several criteria is "shortest remaining processing time first".
> Operating systems don't use it much in practice since few jobs
> volunteer the information in advance.
>
> --
> David Kastrup, Kriemhildstr. 15, 44793 Bochum[/color]

just to add a little sparkling to it - "SORT BY FINISHING TIME and
eliminate overlaps"

[CBFalconer]

Re: greedy method

"Alf P. Steinbach" wrote:[color=blue]
> * David Kastrup:
>
> OT in _four_ of the five groups posted to.[/color]

So do something rather than add to the mess. Set followups and
complain that the OP didn't do that in the first place. Maybe next
time he will.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Stewart Gordon]

[OT] PERT diagrams (was: greedy method)

Ioannis Vranos wrote:
<snip>[color=blue]
> Perhaps you are looking for PERT diagrams?
>
> http://aisweb.wustl.edu/hr/empld.nsf/pages/pert[/color]

I can't quite make sense of this source - why is it the intervals
between tasks, rather than the tasks themselves, that take the time?
[color=blue]
> http://www.netmba.com/operations/project/pert/[/color]

They're quite different from the PERT diagrams from when I went to
college. But with the same basic purpose.

The PERT diagrams of my college days involved boxes like this

+--------------+
| 14 | 3 | 17 |
|--------------|
| Do something |
|--------------|
| 19 | 5 | 22 |
+--------------+

where the boxes are (IIRC)

+---------------------------+
| early | duration | early |
| start | | finish |
|---------------------------|
| task description |
|---------------------------|
| late | slack | late |
| start | | finish |
+---------------------------+

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.

[Stewart Gordon]

[OT] Gantt charts (was: greedy method)

Ioannis Vranos wrote:[color=blue]
> Ioannis Vranos wrote:
>[color=green]
>> There are also GANT diagrams which involve graphic bars.[/color]
>
> GANTT
>
> http://aisweb.wustl.edu/hr/empld.nsf...f?OpenDocument[/color]

That looks more like what I know of as a Gantt chart. Except that the
ones from my college days had arrows on to indicate dependencies.

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.

[Ioannis Vranos]

Re: [OT] PERT diagrams

Stewart Gordon wrote:
[color=blue]
> I can't quite make sense of this source - why is it the intervals
> between tasks, rather than the tasks themselves, that take the time?[/color]


As it is mentioned, the circles represent events in a project. The
problem is, the OP's "jobs" are computer processes or projects? If they
are computer processes, then the subject becomes UML sequence diagrams.


[color=blue][color=green]
>> http://www.netmba.com/operations/project/pert/[/color]
>
>
> They're quite different from the PERT diagrams from when I went to
> college. But with the same basic purpose.
>
> The PERT diagrams of my college days involved boxes like this
>
> +--------------+
> | 14 | 3 | 17 |
> |--------------|
> | Do something |
> |--------------|
> | 19 | 5 | 22 |
> +--------------+
>
> where the boxes are (IIRC)
>
> +---------------------------+
> | early | duration | early |
> | start | | finish |
> |---------------------------|
> | task description |
> |---------------------------|
> | late | slack | late |
> | start | | finish |
> +---------------------------+[/color]


:-)



--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Stewart Gordon]

Re: [OT] PERT diagrams

Ioannis Vranos wrote:[color=blue]
> Stewart Gordon wrote:
>[color=green]
>> I can't quite make sense of this source - why is it the intervals
>> between tasks, rather than the tasks themselves, that take the time?[/color]
>
> As it is mentioned, the circles represent events in a project.[/color]

The first source you cited numbers circles from 1 to 12, and then lists
what look like tasks, not events, again numbered from 1 to 12. So it
seems a plausible interpretation that the numbered list is explaining
the circles. By this, it's indicating that it takes no time to write
the text or to copyedit and format, but it takes time to transition
between the two activities.
[color=blue]
> The problem is, the OP's "jobs" are computer processes or projects? If they
> are computer processes, then the subject becomes UML sequence diagrams.[/color]
<snip>

I don't see any reason a project can't be made up of computer processes.
It happens with me quite a lot.

Moreover, I suppose PERT or similar could be used to evaluate algorithms
involving some element of parallel processing....

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.

[Ioannis Vranos]

Re: [OT] PERT diagrams

Stewart Gordon wrote:
[color=blue]
> The first source you cited numbers circles from 1 to 12, and then lists
> what look like tasks, not events, again numbered from 1 to 12. So it
> seems a plausible interpretation that the numbered list is explaining
> the circles. By this, it's indicating that it takes no time to write
> the text or to copyedit and format, but it takes time to transition
> between the two activities.[/color]


There it is mentioned:

"Circles represent events in a project."

As task in the other link is mentioned the duration itself.


As far as I know the interpretation goes like this:

1. write text (max: 13 days)


After that in parallel:

2. copyedit and format (max: 7 days)
4. take and gather photographs (max: 17 days)

and so on.


[color=blue]
> I don't see any reason a project can't be made up of computer processes.
> It happens with me quite a lot.
>
> Moreover, I suppose PERT or similar could be used to evaluate algorithms
> involving some element of parallel processing....[/color]


Yes I guess so. UML Sequence diagrams can also provide the entire
life-time of objects though.



--
Ioannis Vranos

http://www23.brinkster.com/noicys