| Abstract |
Allocation of resources of an industrial enterprise, aiming to the minimization of the produstion cost, is called Production Scheduling. Each problem of optimal job sequencing (order) in one or more machines, is called Scheduling Problem. In the present work we deal with the solution of one such bicriterion problem: the minimization of the total finishing time and the maximum tardiness of N jobs in one machine, given that the jobs are distributed to B different groups, and a setup time is interposed bet between the executions of two jobs belonging to different groups. Multicriteria Scheduling Problems are in fact a more realistic view of reality compared to one-criterion problems. The most general solution of a multicriteria problem is the computation of the set of efficient solutions, that is, the solutions for which there is no other with better value in one criterion and not worse in the rest. This is the issue to the problem which we deal with in this work. The finding of an efficient solution can be achieved by solving the problem of minimization of the total completion time, given that, according to modified due dates in a right direction adjustment mode, no job will be tardy. This problem does not belong to the class of ordered batch scheduling problems, and so its complexity is exponential to the number of jobs N - not the number of groups B. After the analytical presentation of what we have said until now, we present solution methods of Scheduling Problems which were used in other works (basically, methods to derive lower bounds for a common branch and bound scheme), and we explain the reasons for which none of these methods can be applied to our problem. The main reason for this is the existence of setup times as well as the fact that our problem is not an ordered batch problem. Then we present a comparative study of the most common Dynamic Programming algorithms used for the solution of Scheduling Problems, and we analyze their advantages and disadvantages towards the generally used branch and bound algorithm. The reasons for which we used Dynamic Programming as the solution technique to our problem, as well as the two algorithms implemented, as then presented. We next give the results taken from extended experimentation, and discuss the influence of the number of jobs N, the number of groups B, the position of an efficient solution inside a set of other solutions, and other problem parameters to the solution time. The size of problems (a few more than 20 jobs) for which each efficient solution is found within 1 minute CPU time, is smaller than the size of problems solved, in the same computational time, in order works dealing with Scheduling Problems without setup times (usually around 30 jobs but in a few cases the reach 50). On the other hand, it can be characterized satisfactory when is used for the solution of the problem without the tardiness criterion, and whose solution is one of the efficient solutions of our problem. Finally, we give a general idea for a heuristic algorithm that can solve approximately our bicriterion problem in much less time. We also present a generalization of the Dynamic Programming algorithm that we used to find one efficient solution. This generalized algorithm can solve directly, but with greater complexity, the initial bicriterion problem.
|
Δικριτηριακός Προγραμματισμός Μιας Μηχανής με Χρόνους Εξάρμωσης
