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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\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$ Oct 4, 2019 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$ Oct 6, 2019 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$ Dec 11, 2019 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$ Dec 12, 2019 at 13:23
$\begingroup$
$\endgroup$
1
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.
-
$\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$ Dec 11, 2019 at 20:08