10
$\begingroup$

I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of problems. Understanding this difference would be a good start.

Thanks!

Improve this question
$\endgroup$
7
$\begingroup$

There are three main structural differences between the classic job-shop problem and the classic RCPSP:

1) In the job-shop problem, resource consumption of tasks and capacities of resources (machines) are unitary, i.e. one machine can process only one task at a time. In the RCPSP, resource consumption of tasks and capacities of resources may not be unitary, so in general two tasks demanding the same resource may be executed in parallel.

2) In the job-shop problem, one task (operation) requires only one resource (machine) to be executed. In the RCPSP, one task may require several resources simultaneously to be executed.

3) Precedence constraints form chains in the job-shop problem, tasks forming a chain are called operations and the set of tasks forming a chain is called a job. Different operations of the same job require different machines for execution. In the RCPSP, the precedence constraints can form any acyclic graph.

Improve this answer
$\endgroup$
  • $\begingroup$ So regarding (3): a chain of sequential tasks is a job - but what if there is some kind of branching in the job logic sequence where an upstream chain leads to two separate branches? Would this be 3 jobs, each with a serial sequence of unique operations, or would it be 2 jobs where each job shares a few operations with the other job? The concept of jobs vs operations is elusive in introductory discussions of this. Thanks! $\endgroup$ – Isaac Howenstine Oct 4 '19 at 16:35
  • 1
    $\begingroup$ If there is "branching" as you define it, then the problem is not job-shop anymore. Thus, definitions of jobs and operations does not apply here. $\endgroup$ – Ruslan Sadykov Oct 6 '19 at 17:46
  • $\begingroup$ just to clarify, does that mean that if the operations not in a direct, ordered sequence, then this is not a job-shop? For example, here: link, the precedence branches, where some parallelism is possible, and then the precedence reconvenes at the completion of the job. According to the precise definition, then this is not a job-shop. Is this correct? $\endgroup$ – Isaac Howenstine Dec 11 '19 at 19:58
  • $\begingroup$ In this link precedences incident to the source and the sink are not precedences between two tasks, they are artificial and do not count as precedence relations. This is job-shop. $\endgroup$ – Ruslan Sadykov Dec 12 '19 at 13:23
4
$\begingroup$

From a practical point of view, Job shop scheduling defines as, processing of specific jobs on the machines in some stages which is called route (maybe involve reverse routes), That even may contain more than one machine in each stage (hybrid models).

Resource-constrained project scheduling defines as, allocate tasks to the resources that, in general, don't have a specific route.

In the job shop scheduling, the objective is to find an optimum sequence of the jobs on the machine (in each stage) to minimize specific aims (E.g. makespan). but in the RCPS, tasks are usually predefined by users and objective is to minimize the duration of the project. In the job shop models, sequencing of the processes is important while in the RCPS it may be or may not. Job shops (or hybrid) scheduling arise in the manufacturing system as a detailed schedule while RCPS comes from projects planning.

Indeed, you could find many related issues by googling. If you are interested to develop a practical scheduling model, I recommended the below reference.

Planning and Scheduling in Manufacturing and Services

Improve this answer
$\endgroup$
  • $\begingroup$ You said "Resource-constrained project scheduling defines as, allocate tasks to the resources that, in general, don't have a specific route." But a "route" seems to be unique to a job, which is "routed" to machines which conduct operations according to the precedence rules. This is confusing to me, can you clarify? Also, thank you for the reference to the book it's been very helpful. $\endgroup$ – Isaac Howenstine Dec 11 '19 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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