Trouble with scheduling problem assumptions

Question

Reading the famous book by Pinedo, I came across :

Usually, the subscript $j$ refers to a job while the subscript $i$ refers to a machine. If a job requires a number of processing steps or operations then the pair $(i,j)$ refers to the processing step or operation of job $j$ on machine $i$.

Then he defines the processing time :

The $p_{ij}$ represents the processing time of job $j$ on machine $i$.

On the other hand, Brucker defines the processing time as follows :

A job $j$ consists of $n_j$ operations $O_{j1},..,O_{jn_j}$. Associated with operation $O_{ji}$ a processing time $p_{ij}$

N.B: here $i$ indicates the operations and not the machines.

Then,

Associated with each operation $O_{ji}$ a set of machines $\mu_{ji} \subseteq \{M_1,..,M_m\}$. $O_{ji}$ may be processed on any machine in $\mu_{ji}$. Usually, all $\mu_{ji}$ are one element sets or all $\mu_{ji}$ are equal to the set of all machines. In the first case, we have dedicated machines. In the second case, the machines are called parallel.

The definitions are not the same. For example, if a job $j$ consists of two operations $O_{j1}, O_{j2}$, two possible cases are creating confusion :

1. If one operation can be done by the same machine, using the definition of Brucker is not sufficient. Indeed, in addition to the job and operation indices, we need a third one indicating the machine (the processing time can differ from one machine to another)

2. If the two operations can be done by the same machine, the processing time definition by Pinedo is not sufficient we need an additional index for the operation.

I think that Bruker is somehow assuming that all machines are identical and Pinedo is somehow assuming that a machine can only do one operation and each operation can be done by only one machine. In other terms, there is a one-to-one function that maps operations to machines. Or, eventually, we define an equivalence relation $\mathcal{R}$ as follows $x \mathcal{R} y \Leftrightarrow$ machines $x$ and $y$ have the same speed. In this case, Pinedo is somehow assuming that there is a one-to-one mapping between operations and the quotient set. Thus, there is no need to talk about the operations index.

Any help to clarify the situation? Or even any suggestion for a reference that may be less ambiguous?

N.B. This may be a dumb question, but I have a pure mathematics background, where everything is defined the same way nearly everywhere. Coming across multiple definitions without precising the underlying assumptions is a huge frustration for me.

Answer 1

In Pinedo's book, on page 13 (directly above your quotation) it says:

"Over the last fifty years a considerable amount of research effort has been focused on deterministic scheduling. The number and variety of models considered is astounding. During this time a notation has evolved that succinctly captures the structure of many (but for sure not all) deterministic models that have been considered in the literature.
  The first section in this chapter presents an adapted version of this notation. The second section contains a number of examples and describes some of the shortcomings of the framework and notation.".

In Brucker's book, on page 3 (the next page, after your quote), it says:

"In general, all data $p_i$, $p_{ij}$, $r_i$, $d_i$, $w_i$ are assumed to be integer. A schedule is feasible if no two time intervals overlap on the same machine, if no two time intervals allocated to the same job overlap, and if, in addition, it meets a number of problem-specific characteristics. A schedule is optimal if it minimizes a given optimality criterion.
  Sometimes it is convenient to identify a job $J_i$ by its index $i$. We will use this brief notation in later chapters.
  We will discuss a large variety of classes of scheduling problems which differ in their complexity. Also the algorithms we will develop are quite different for different classes of scheduling problems. Classes of scheduling problems are specified in terms of a three-field classification $\alpha | \beta | \gamma$ where $\alpha$ specifies the machine environment, $\beta$ specifies the job characteristics, and $\gamma$ denotes the optimality criterion. Such a classification scheme was introduced by Graham et al. [108].
[108] R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287–326, 1979.".

I think that Bruker is somehow assuming that all machines are identical and Pinedo is somehow assuming that a machine can only do one operation and each operation can be done by only one machine. ... Any help to clarify the situation? Or even any suggestion for a reference that may be less ambiguous?

N.B. This may be a dumb question, but I have a pure mathematics background, where everything is defined the same way nearly everywhere. Coming across multiple definitions without precising the underlying assumptions is a huge frustration for me.

Each author presents a method and algorithm for various aspects of similar and differing problems, and each adapts a notation used previously or creates their own (usually with justification as to why it's necessary).

Coincidentally Brucker explains that people share your concern in: "Resource-constrained project scheduling: Notation, classification, models, and methods", European Journal of Operational Research Volume 112, Issue 1, 1 January 1999, Pages 3-41:

"So far, no classification scheme exists which is compatible with what is commonly accepted in machine scheduling. Also, a variety of symbols are used by project scheduling researchers in order to denote one and the same subject. Hence, there is a gap between machine scheduling on the one hand and project scheduling on the other with respect to both, viz. a common notation and a classification scheme. As a matter of fact, in project scheduling, an ever growing number of papers is going to be published and it becomes more and more difficult for the scientific community to keep track of what is really new and relevant. One purpose of our paper is to close this gap. That is, we provide a classification scheme, i.e. a description of the resource environment, the activity characteristics, and the objective function, respectively, which is compatible with machine scheduling and which allows to classify the most important models dealt with so far. Also, we propose a unifying notation.

Definition of "exact science":

"Noun: exact science (plural: exact sciences)

1. (sciences, narrowly) A mathematical science, i.e. a field of science such as mathematics or mathematical physics which is capable of perfectly exact results based on rigorously formal methods.

2. (sciences, broadly) A field of science such as physics or chemistry that is not perfectly exact, but still capable of highly quantitative results based on methods that are are not strictly rigorous, but still systematic and scrupulous.

Usage notes: Often used in the form of litotes when something is far from being an exact science.".

Some things are simple or can only work one way, thus rigorous standardization is not only desirable but possible. Other things are discovered in isolation and are complex, resulting in each person or group having their own language and methods.

Arguably one of the first things mankind discovered was soil, rock, or the Sun. Each language doesn't use the same word to represent the same concept despite their universality.

The 2015 Ig Nobel Prize Winners for Literature was awarded to Mark Dingemanse [The Netherlands, USA], Francisco Torreira [Spain, The Netherlands, Belgium, USA, Canada], and Nick J. Enfield [Australia, The Netherlands], for discovering that the word “huh?” (or its equivalent) seems to exist in every human language — and for not being completely sure why.

Reference: “Is ‘Huh?’ a universal word? Conversational infrastructure and the convergent evolution of linguistic items”, Mark Dingemanse, Francisco Torreira, and Nick J. Enfield, PLOS ONE, 2013. [a video accompanies the paper.]

Who attended the ceremony: The authors were unable to attend the ceremony; they sent a video acceptance speech. They received their prize at a special event (The European Ig Nobel Show) in Amsterdam, The Netherlands on October 3.

Max Planck Institute for Psycholinguistics, "Is "huh" a universal word?".

Personal opinion: In English "huh" has two meanings - "what" and "understood".

Answer 2

Fattahi et al., in their paper¹, defined the decision variable that you mentioned in your question as follow:

$a_{ijh} = \begin{cases} 1 & \text{ if} \ \ O_{jh} \ \text{can be performed on machine }i \\ 0 & \text{ if otherwise} \\ \end{cases}$

Even more, they make their model more general by defining various priority for the job $j$ for which the operation $h$ is decided to be done on machine $i$ on priority $k$.

[1] Fattahi, Parviz, Mohammad Saidi Mehrabad, and Fariborz Jolai. "Mathematical modeling and heuristic approaches to flexible job shop scheduling problems." Journal of intelligent manufacturing 18.3 (2007): 331-342.

Answer 3

From a practical point of view, Scheduling models have own definitions according to the structure of the problem under study. Both definitions above are true and have been mentioned based on two different approaches. If you are interested to survey such explanations you could find lots of models and definitions in the literature. As Rob and Oguz mentioned too.