Algorithms for scheduling a single machine to minimize total completion time and total tardiness

الملخص EN

In this paper we look at the problem where we have to schedule n jobs with processing times and due dates on a single machine.

The objective is to find a schedule that minimize a function of the sum of completion time and sum of tardiness (i,e to minimize the multiple objective functions (Ci,Ti)).

We propose two methods for solving this simultaneous minimization problem to find the set of all efficient solutions, (Pareto optimal solutions).

This set of all efficient solutions is not easy to find, therefore, it could be preferable to have an approximation to that set in a reasonable amount of time.

Therefore branch and bound (BAB) and local search methods are used.

The Particle Swarm Optimization (PSO) method is applied as new local search method on a set of randomly generated problems to solve machine scheduling problem with multiple objective functions.

Comparison studies are made between Branch and Bound Methods (BAB), PSO and Genetic Algorithm (GA) to show which one is the better method in applications.

In addition, tuning the parameters of every method has been suggested in order to improve the application of every method.

A new style of development steps has been proposed to achieve good convergence in application.

Since our problem is NP-hard, we propose new heuristic method like PSO and GA to find approximation solutions especially when the number of jobs exceeds the ability of some exact methods like complete enumeration and BAB in solving such problems.

Lastly, the proposed methods results are compared for this multi-objective scheduling problem.

Computational experience is found that these local search algorithms solve problem to '2000 'jobs with reasonable time.