# Computing Idle Times in Fuzzy Flexible Job Shop Scheduling
## 2 The Fuzzy Flexible Job Shop Problem
### Fuzzy Schedules  
A solution to the problem, commonly called a schedule and denoted as \(\phi=(\tau_{\phi},\mathbf{s}_{\phi})\), consists of both a resource assignment, \(\tau_{\phi}\), and a starting time assignment, \(\mathbf{s}_{\phi}\), for all operations. This solution is feasible if and only if all precedence and capacity constraints hold. More formally, for an operation, \(o\in\mathbf{O}\), let \(\tau_{\phi}(o)\) be the resource to which it is assigned in \(\phi\), and let \(\widehat{s_{\phi}}(o)\) and \(\widehat{c_{\phi}}(o)=\widehat{s_{\phi}}(o)+\widehat{p}(o,\tau_{\phi}(o))\) be, respectively, its starting and completion times in the solution \(\phi\). Then, precedence constraints hold for \(\phi\) if and only if, for any pair of operations, \(o,u\in\mathbf{O}\),  
\[\widehat{c_{\phi}}(o)\preceq\widehat{s_{\phi}}(u)\text{ when }\chi(o)=\chi(u), \eta(o)<\eta(u) \tag{8}\]  
and capacity constraints hold if and only if  
\[\tau_{\phi}(o)\in\mathbf{R}(o) \tag{9}\] \[\widehat{c_{\phi}}(o)\preceq\widehat{s_{\phi}}(u)\vee\widehat{c_{ \phi}}(u)\preceq\widehat{s_{\phi}}(o)\text{ when }\tau_{\phi}(o)=\tau_{\phi}(u). \tag{10}\]  
Notice that a feasible starting time assignment, \(\mathbf{s}_{\phi}\), induces an ordering for all the operations in the same resource. In the sequel, given a resource, \(r\in\mathbf{R}\), let \(\alpha_{\phi}(r)\) denote the first operation to be processed in \(r\) according to schedule \(\phi\), and let \(\omega_{\phi}(r)\) be the last operation to be processed in \(r\). Also, for an operation, \(o\in\mathbf{O}\), let \(JP(o)\) (resp. \(JS(o)\)) denote its immediate predecessor (resp. successor) in its job, \(RP_{\phi}(o)\) (resp. \(RS_{\phi}(o)\)) its immediate predecessor (resp. successor) in its resource according to the ordering induced via \(\phi\), and \(\widehat{p_{\phi}}(o)=\widehat{p}(o,\tau_{\phi}(o))\) the operation's processing time in the resource to which it is assigned.  
A feasible schedule is semi-active if no operation, \(o\), can start earlier (in the sense that it can be assigned another starting time, \(\widehat{s}^{\prime}(o)\), such that \(\widehat{s}^{\prime}(o)\preccurlyeq\widehat{s}_{\phi}(o)\)) without changing the order of processing on any of the resources. In consequence, for a semi-active schedule, the starting time of any operation, \(o\), is the earliest starting time of that operation according to the job and resource processing orders:  
\[\widehat{s}_{\phi}(o)=\max\{\widehat{c}_{\phi}(JP(o)),\widehat{c}_{\phi}(RP_{ \phi}(o))\} \tag{11}\]  
where \(\widehat{c}_{\phi}(JP(o))\) (resp. \(\widehat{c}_{\phi}(RP_{\phi}(o))\)) is taken to be \((0,0,0)\) if \(\eta(o)=\min\{\eta(u):\chi(u)=\chi(o)\}\), that is, \(o\) is the first operation in its job (resp. \(o\) is the first operation in its resource, \(o=\alpha_{\phi}(\tau_{\phi}(o))\)).  
For so-called regular objective functions (those which are non-decreasing functions of the jobs' completion times), optimal schedules are necessarily semi-active. Assuming semi-active schedules reduces the total number of feasible schedules from infinity to a finite (albeit possibly large) number, with each set of resource orderings providing a single semi-active schedule. For this reason, it is common in the scheduling literature to consider only semi-active schedules. Unless otherwise stated, this will also be assumed here.