2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The graph consisting of all vertices corresponding to a particular machine and the induced chosen edges form a directed path. This path tells you exactly which jobs to run on that machine and in what order.

The length of the longest weighted path from u to a job tells you exactly when you can start processing that job.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is true, but there are precedence constraints on operations between machines. So you don't know at what time a machine starts its operation just by looking at the order within the cliques. Maybe I'm asking for too much here, but what I want is a sort of timeline for operations on each machine (akin to the information available in a GANTT chart, for example) $\endgroup$
    – Micrified
    Commented Mar 19, 2021 at 13:16
  • $\begingroup$ @Micrified This is what the second part of my answer takes care of. If you want to know when to process a task, compute the length of the longest path from u to that task in the whole graph (with precedence edges). This will ensure that a task is only started when the prerequesites are met. $\endgroup$
    – Tassle
    Commented Mar 19, 2021 at 13:23
  • $\begingroup$ Oh, I see what you mean now! I had simply pigeonholed the length of the longest path as being useful only for obtaining the makespan and didn't realise you could use the elements of the path to know when tasks would start! Thank you $\endgroup$
    – Micrified
    Commented Mar 19, 2021 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.