Abstract : This paper deals with due date assignment and just-in-time scheduling for single machine and parallel machine problems with equal-size jobs where the objective is to minimize the total weighted earliness-tardiness and due date cost. These two problems, but with a common due date to be calculated, were shown to be polynomially solvable in O(n^4) time. We first show that this complexity can be reduced to O(n^3) by modeling the single machine scheduling problem as an assignment problem without necessary due date enumeration. We next prove that the general case with identical parallel machines and a given set of assignable due dates where the cardinality of this set is bounded by a constant number is still polynomially solvable.
https://hal-univ-tours.archives-ouvertes.fr/hal-01003789
Contributeur : Vincent T'Kindt
<>
Soumis le : mardi 10 juin 2014 - 16:32:05
Dernière modification le : mercredi 21 mars 2018 - 10:54:07
