# Scheduling a Single Machine with Primary and Secondary Objectives
## 5 Scheduling the Bins
Thus, the overall cost for the construction of all the bins is \(O(n^{2}\log n)\), which is also the cost of the overall scheme since the kernel jobs are scheduled by the ED heuristics. Note that the second condition in the above theorem is sufficient, but not necessary for minimizing the makespan; i.e., some bins in a feasible schedule respecting threshold \(L(\delta)\) may have idle time intervals, but that schedule may minimize the makespan. In general, we rely on the efficiency of the heuristics used for packing our bins for the minimization of the makespan criterion. We also straightforwardly observe that by the DNF heuristics, no unscheduled job may fit within any available gap in any bin without forcing some other job to surpass the current allowable lateness \(L(\delta)\) at Phase 1, whereas the DNF-heuristics tends to keep reserved \"short\" unscheduled jobs. Continuing with the issue of the practical behavior, as we have mentioned in the Introduction, the ED heuristics turns out to be an efficient tool for a proper distribution of the jobs within the bins. In [9], computational experiments were conducted for 200 randomly generated instances of our problem. For the majority of these instances, the forced delay of kernel \(K(S)\) in the initial ED-schedule \(S\) (i.e., the difference between the completion time of the corresponding delaying emerging job and \(r(K)\)) was neglectable. Therefore, the lateness of the corresponding overflow job was either optimal or very close to the optimal maximum job lateness (as no job of kernel \(K\) can be started earlier than at time \(r(K)\) in any feasible solution). At the same time, since the ED heuristics creates no avoidable machine idle time interval, the minimum makespan is also achieved. Thus, for the majority of the tested problem instances, both objective criteria were simultaneously minimized or the maximum jobs lateness was very close to the optimum, whereas the makespan was optimal. The computational experiments from [9] also yield that, for most of the tested instances, already for small trial \(\delta\)'s, the bins would have been scheduled in Phase 1 (i.e., no IA(b2) would arise). Moreover, there will be no avoidable gap left within the bins for these \(\delta\)'s. In other words, the conditions in Theorem 2 would be satisfied, and Phase 1 would successfully completed. In theory, however, we cannot guarantee such a behavior, and we proceed with our construction in Phase 2. Phase 2: If the first condition in Theorem 2 is not satisfied, i.e., an IA(b2) at the first pass of Phase 1 occurs, then Phase 2 is invoked. Let \(y\) be the earliest arisen Type (b) y-job that could not have been included in schedule \(S(B,y)\). In general, job \(j\) may be pushed by one or more other Type (b) y-jobs. Since the lateness of job \(y\) surpasses \(L(\delta)\), a complete schedule respecting this threshold value cannot be created unless the lateness of job \(y\) is decreased. The next observation follows:  
**Observation 6**. : _Suppose an IA(b2) with (a Type (b) y-job) \(y\) at the first pass of Phase 1 in bin B arises. Then, the resultant maximum job lateness in bin B yielded by job y cannot be decreased unless job y and/or other Type (b) y-jobs currently pushing job y in bin B are rescheduled to some earlier bin(s)._  
According to the above observation, in Phase 2, either job \(y\) is to be rescheduled to an earlier bin or a subset of the above Type (b) y-jobs (with an appropriate total processing time) is to be formed and all jobs from that subset are to be rescheduled to some earlier bin(s). In particular, if the lateness of job \(y\) surpasses \(L(\delta)\) by amount \(\lambda\), then the total processing time of jobs in such a subset is to be at least \(\lambda\). By the construction, no new job can feasibly be introduced into any already scheduled bin \(B\) unless some jobs (with an appropriate total length) from that bin are rescheduled behind all the above Type (b) y-jobs.