2018/02/28 by Gais Alhadi, Alhadi, Gais, Imed Kacem +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1802.10488
submitted to Sose 2018
arxiv created 2018/02/28 · openalex publication_date 2018/02/28 · arxiv updated 2018/03/01 · openalex created_date 2018/03/06 · openalex updated_date 2026/07/28
We consider the two-parallel machines scheduling problem, with the aim of minimizing the maximum lateness and the makespan. Formally, the problem is defined as follows. We have to schedule a set J of n jobs on two identical machines. Each job i in J has a processing time pi and a delivery time qi. Each machine can only perform one job at a given time. The machines are available at time t=0 and each of them can process at most one job at a given time. The problem is to find a sequence of jobs, with the objective of minimizing the maximum lateness Lmax and the makespan Cmax. With no loss of generality, we consider that all data are integers and that jobs are indexed in non-increasing order of their delivery times: q1 >= q2 >= ... >= qn. This paper proposes an exact algorithm (based on a dynamic programming) to generate the complete Pareto Frontier in a pseudo-polynomial time. Then, we present an FPTAS (Fully Polynomial Time Approximation Scheme) to generate an approximate Pareto Frontier, based on the conversion of the dynamic programming. The proposed FPTAS is strongly polynomial. Some numerical experiments are provided in order to compare the two proposed approaches.