English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the two-parallel machines scheduling problem, with the aim ofminimizing the maximum lateness and the makespan. Formally, the problem isdefined as follows. We have to schedule a set J of n jobs on two identicalmachines. Each job i in J has a processing time p_i and a delivery time q_i.Each machine can only perform one job at a given time. The machines areavailable at time t=0 and each of them can process at most one job at a giventime. The problem is to find a sequence of jobs, with the objective ofminimizing the maximum lateness L_max and the makespan C_max. With no loss ofgenerality, we consider that all data are integers and that jobs are indexed innon-increasing order of their delivery times: q_1 >= q_2 >= ... >= q_n. Thispaper proposes an exact algorithm (based on a dynamic programming) to generatethe complete Pareto Frontier in a pseudo-polynomial time. Then, we present anFPTAS (Fully Polynomial Time Approximation Scheme) to generate an approximatePareto Frontier, based on the conversion of the dynamic programming. Theproposed FPTAS is strongly polynomial. Some numerical experiments are providedin order to compare the two proposed approaches.

An Approximate Pareto Set for Minimizing the Maximum Lateness and Makespan on Parallel Machines