# Scheduling a Single Machine with Primary and Secondary Objectives
## 5 Scheduling the Bins
Such a job, which we call a substitution job for job \(y\), should clearly be an emerging job for job \(y\), i.e., \(d_{s}>d_{y}\) (as otherwise, once rescheduled, its lateness will surpass \(L(\delta)\)). **Theorem 3**. : _If for an IA(b2) with a (Type (b) y-job) \(y\), there exists no substitution job for job \(y\), then there exists no feasible schedule respecting threshold value \(L(\delta)\). Hence, there exists no Pareto-optimal solution with maximum job lateness \(L(\delta)\)._  
Proof. : Due to Observation 6, job \(y\) or some other Type (b) y-job(s) pushing job \(y\) must be rescheduled to a bin preceding bin \(B\). By the way we construct our bins, no new job can feasibly be introduced into any bin preceding bin \(B\) unless some (sufficiently long) job \(s\) from that bin is rescheduled behind all the above Type (b) y-jobs. \(d_{s}<d_{y}\) must hold as otherwise job \(s\) or some job originally included before job \(y\) will surpass the current threshold; i.e., \(s\) is a substitution job. It follows that if there exists no substitution job, the lateness of at least one job from bin \(B\) or from its preceding bin will surpass threshold value \(L(\delta)\), and hence, there may exist no feasible schedule respecting \(L(\delta)\). The second claim immediately follows. Due to the above theorem, if these exists no substitution job, the call from the binary search procedure for the current \(\delta\) halts with the failure outcome, and the procedure proceeds with the next (larger) trial value for \(\delta\); if there remains no such \(\delta\), the whole scheme halts. The case when there exists a substitution job for job \(y\) is discussed now. We observe that there may exist a Pareto-optimal solution. To validate whether it exists, we first need to verify if there exists a feasible solution respecting threshold \(L(\delta)\) (given that the call to the bin packing procedure was performed from the iteration in the binary search procedure with that threshold value). This task is easily verified if, for instance, there is a single substitution job \(s\). Indeed, we may construct an auxiliary ED-schedule in which we activate that substitution job for job \(y\) (similarly as before, we increase artificially the release time of job \(s\) to that of job \(y\), so that once the ED heuristics is newly applied to that modified problem instance, the substitution job \(s\) will be forced to be rescheduled behind job \(y\)). In the resultant ED-schedule with the activated job \(s\), if the lateness of none of the rescheduled y-jobs is no greater than \(L(\delta)\), Phase 1 can be resumed for bin \(B\). Otherwise, there may exit no feasible solution respecting threshold \(L(\delta)\) (hence, no Pareto-optimal solution with the maximum job lateness not exceeding \(L(\delta)\) may exist), and the scheme can proceed with the next trial \(\delta\). In practice, with a known upper limit on the total number of substitution jobs, the above activation procedure can be generalized to another procedure that enumerates all the possible subsets of substitution jobs in polynomial time. In general, if the number of substitution jobs is bounded only by \(n\), the number of possible subsets of substitution jobs with total processing time \(\lambda\) or more might be an exponent of \(n\). In theory and practice, we may take one of the two alternative options: either we try all such possible non-dominated subsets building an implicit enumerative algorithm, or we may rather choose a heuristic approach generating a fixed number of \"the most promising\" subsets of substitution jobs in polynomial time. Based on our general framework, both implicit enumeration and heuristic algorithms might be implemented in different ways. The study of such algorithms, which would rely on the results of numerical experiments, is beyond the scope of this paper and could rather be a subject of independent research.