Meta-heuristic Algorithm for Bounded-Splitting Jobs Scheduling Problem on a Single Machine

This presentation deals with scheduling problem with availability constraints on a single machine. The jobs are splitable into sub-jobs and a common lower bound on the size of each sub-job is imposed. The objective function aims to find a feasible schedule that minimizes the maximum completion time of jobs. The proposed scheduling problem was proved from be strongly NP-hard by a reduction to 3-SAT problem. We propose some effective heuristics are BMF - Based on Max Flow resolution and MAAS - MAtching and ASsignment approach.

After that we apply Genetic Algorithm on BMF and MAAS and the last we use the. Net Parallel Task Library to evaluate the population. The computational results show the performance of the proposed heuristics in comparing with the exact method proposed in the literature.