Skip to main content
Computer Science

Return to Question

added 104 characters in body
Source Link
Micrified
Micrified
  • 123
  • 5

Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

enter image description here

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

enter image description here

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

Verdict

In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?

Edit: There's a mistake in my graph, the last edges going to $V$ should be labelled with a weight.

Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

enter image description here

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

enter image description here

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

Verdict

In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?

Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

enter image description here

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

enter image description here

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

Verdict

In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?

Edit: There's a mistake in my graph, the last edges going to $V$ should be labelled with a weight.

Source Link
Micrified
Micrified
  • 123
  • 5

Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

enter image description here

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

enter image description here

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

Verdict

In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?