• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Препринт

Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times

Lazarev A. A., Arkhipov D. I., Werner F.
The following special case of the classical NP-hard scheduling problem 1jrj jLmax is considered. There is a set of jobs N = f1; 2; : : : ; ng with identical processing times pj = p for all jobs j 2 N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1jrj jCmax, presented by Garey et al. (1981) and Simons (1978) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q _ n log n) and O(n2 log n), respectively, where 10􀀀Q is the accuracy of the input-output parameters.