# Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
## 1 Introduction  
This paper addresses a variant of classical shop scheduling models. While, in classical job shop or flow shop (as well as in the large majority of scheduling problems with precedence constraints), the task of a job cannot start before the previous task of the same job has _finished_, we address a situation in which each task of a job cannot start before the previous task of the same job has _started_. These types of constraints are known in the literature as _s-precedence constraints_. Scheduling problems with s-precedence constraints have been introduced by [PERSON] and [PERSON] [1] in the case of parallel machines. They showed that makespan minimization is NP-hard, and developed a heuristic procedure deriving tight worst-case bounds on the relative error. [PERSON], [PERSON], and [PERSON] [2] performed a similar analysis when the objective was the minimization of total completion time of the tasks, while [PERSON] [3] extended the analysis to uniform machines. [PERSON] [4] analyzed a parallel-machine problem in which traditional finish-start precedence constraints coexisted with s-precedence constraints (that she renamed _selfish precedence constraints_, giving an enjoyable dramatized motivation of the model), and established various worst-case bounds for classical dispatching rules which refer to specific structures of precedence constraints. Indeed, s-precedence constraints also arise in project management, called _start-start_ precedence constraints ([PERSON] and [PERSON] [5]), as a result of the elaboration of a work breakdown structure (WBS) and of the coordination among different operational units. To our knowledge, none has addressed job shop and flow shop problems with s-precedence constraints so far.  
The problem can be formally introduced as follows. We are given a set of \(n\)\(h\)\(J^{1},J^{2},\ldots,J^{n}\), to be processed on a shop with \(m\) machines denoted as \(M_{1},\ldots,M_{m}\). Each job \(J^{k}\) consists of a totally ordered set of _tasks_, \(J^{k}=\{O_{1}^{k},O_{2}^{k},\ldots,O_{n_{k}}^{k}\}\), \(k=1,\ldots,n\). Task \(O_{i}^{k}\) requires processing time \(p_{i}^{k}\) on a given machine \(M(O_{i}^{k})\), \(i=1,\ldots,n_{k}\). Tasks cannot be preempted. Task \(O_{i}^{k}\) can only start after task \(O_{i-1}^{k}\) is started; i.e., there is an s-precedence constraint between tasks \(O_{i-1}^{k}\) and \(O_{i}^{k}\), for all \(k=1,\ldots,n\), \(i=2,\ldots,n_{i}\)A _schedule_ is an assignment of starting times to all tasks so that at any time each machine processes at most one task and all s-precedence constraints are satisfied. The problem is to find a feasible schedule that minimizes makespan.  
We characterize the complexity of special cases of the problem, considering a fixed number of jobs and machines. Shop problems with few jobs occur when modeling synchronization and conflicts among processes share common resources. Examples of this situation include scheduling robot moves in flexible robotic cells ([PERSON] et al [6]), aircraft scheduling during taxiing at an airport so that no aircraft collides ([PERSON] et al. [7]), or, in container terminals, the synchronization of crane gantry movements once transportation tasks have been assigned ([PERSON] and [PERSON] [8]).  
The structure of the paper is as follows. In Section 2 we consider the job shop scenario, and give a polynomial time algorithm for the problem in which \(n=2\), \(m=2\), and each job can visit the machines several times (that is, _recirculation_[9] is allowed ). In Section 3 we focus on the flow shop scenario. We show that the two-machine flow shop can be solved in linear time and we give a polynomial time algorithm for the \(m\)-machine problem with two jobs. In Section 4 we briefly discuss cases with \(n>2\) and point out open problems.