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]

* santosh:
OT.

 

[David Kastrup]

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...

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.

 

[Alf P. Steinbach]

* David Kastrup:
OT in _four_ of the five groups posted to.

 

[Ioannis Vranos]

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...

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]

Perhaps you are looking for PERT diagrams?

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

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

There are also GANT diagrams which involve graphic bars.

 

[Ioannis Vranos]

There are also GANT diagrams which involve graphic bars.

GANTT

http://aisweb.wustl.edu/hr/empld.ns...74dc34f588656cf286256f3900692f0f?OpenDocument

 

[puzzlecracker]

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.

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

 

[puzzlecracker]

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.

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

 

[CBFalconer]

* David Kastrup:

OT in _four_ of the five groups posted to.

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.

 

[Stewart Gordon]

Ioannis Vranos wrote:

Perhaps you are looking for PERT diagrams?

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

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?

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

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.

 

[Stewart Gordon]

GANTT

http://aisweb.wustl.edu/hr/empld.ns...74dc34f588656cf286256f3900692f0f?OpenDocument

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.

 

[Ioannis Vranos]

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?

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.

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 Gordon]

As it is mentioned, the circles represent events in a project.

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.

The problem is, the OP's "jobs" are computer processes or projects? If they
are computer processes, then the subject becomes UML sequence diagrams.

<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.

 

[Ioannis Vranos]

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.

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.

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....

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