By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,068 Members | 1,734 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,068 IT Pros & Developers. It's quick & easy.

greedy method

P: n/a
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...

Nov 14 '05 #1
Share this Question
Share on Google+
14 Replies


P: n/a
* santosh:


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?
Nov 14 '05 #2

P: n/a
"santosh" <sa**********@gmail.com> writes:
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.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Nov 14 '05 #3

P: n/a
* David Kastrup:


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?
Nov 14 '05 #4

P: n/a
santosh wrote:
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

http://www23.brinkster.com/noicys
Nov 14 '05 #5

P: n/a
Ioannis Vranos wrote:
There are also GANT diagrams which involve graphic bars.


GANTT

http://aisweb.wustl.edu/hr/empld.nsf...f?OpenDocument

--
Ioannis Vranos

http://www23.brinkster.com/noicys
Nov 14 '05 #6

P: n/a
Ioannis Vranos wrote:
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

http://www23.brinkster.com/noicys
Nov 14 '05 #7

P: n/a

David Kastrup wrote:
"santosh" <sa**********@gmail.com> writes:
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.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum


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

Nov 14 '05 #8

P: n/a

David Kastrup wrote:
"santosh" <sa**********@gmail.com> writes:
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.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum


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

Nov 14 '05 #9

P: n/a
"Alf P. Steinbach" wrote:
* 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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #10

P: n/a
Ioannis Vranos wrote:
<snip>
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.

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

P: n/a
Ioannis Vranos wrote:
Ioannis Vranos wrote:
There are also GANT diagrams which involve graphic bars.


GANTT

http://aisweb.wustl.edu/hr/empld.nsf...f?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.

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

P: n/a
Stewart Gordon wrote:
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.
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 |
+---------------------------+

:-)

--
Ioannis Vranos

http://www23.brinkster.com/noicys
Nov 14 '05 #13

P: n/a
Ioannis Vranos wrote:
Stewart Gordon wrote:
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 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.

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

P: n/a
Stewart Gordon wrote:
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.

--
Ioannis Vranos

http://www23.brinkster.com/noicys
Nov 14 '05 #15

This discussion thread is closed

Replies have been disabled for this discussion.