My Thesis

In this thesis, we presented two branch-and-bound algorithms for the exact resolution of the identical parallel machine scheduling problem with heads and tails, denoted by P|rj, qj |Cmax. The importance of this strongly NPhard problem is twofold. Firstly, it generalizes several well-known parallel machine scheduling problems. Secondly, it plays a crucial role in solving more complex scheduling problems. Moreover, this problem arises in several practical applications. The only algorithm proposed to solve exactly the P|rj, qj |Cmax is the one presented by Carlier (1987).

A new preprocessing algorithm devised to simplify the problem by reducing the number of unscheduled jobs is proposed. This algorithm plays a crucial role in accelerating the convergence of the proposed branch-andbound algorithms. New lower bounding strategies are investigated for the P|rj, qj |Cmax. In particular, a new bounding scheme based on relaxing the problem as a parallel machine scheduling problem with availability constraints is proposed. Also, a new bin-packing based lower bound, as well as several new lifting procedures are derived. Moreover, we introduce the new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|rj, qj |Cmax which dominates the well-known preemptive lower bound. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.

The first proposed branch-and-bound algorithm is based on time windows. This algorithm embodies the best derived lower bound as well as the proposed preprocessing algorithm. Also, new procedures that construct improved approximate schedules are incorporated in the algorithm. Moreover, an effective algorithm that aims at adjusting the parameters of the problem and identifying the inconsistencies as well as strengthening the lower bounds is embedded in the branch-and-bound algorithm. Furthermore, an original pseudo-parallel implementation based on the symmetry of the P|rj, qj |Cmax is proved to be very useful for the efficiency of the algorithm. Extensive computational experiments show that although the two algorithms are timewindows-based, our algorithm consistently outperforms Carlier’s one.

The second proposed branch-and-bound algorithm is based on a new original representation of the P|rj, qj |Cmax as a sequencing problem. Indeed, we show that specifying an order between the different jobs suffices to build a feasible schedule. This problem formulation enables us to derive several rules that consistently reduce the size of the search tree. Also, we show how a strong network-flow-based relaxation scheme can be derived through a generalization of the semi-preemptive lower bound. Moreover, new effective heuristics are shown to be of a capital importance for the efficiency of the branch-and-bound algorithm. Our experimental results show that this new algorithm makes it possible to solve up to 1500 jobs-50 machine instances in a small CPU time, whereas previous algorithms could not even solve instances with 50 jobs and 2 machines. This result constitutes a significant step toward efficient solutions of NP-hard parallel machine scheduling problems.