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

This paper considers the problem of scheduling jobs on single and parallelmachines where all the jobs possess different processing times but a common duedate. There is a penalty involved with each job if it is processed earlier orlater than the due date. The objective of the problem is to find the assignmentof jobs to machines, the processing sequence of jobs and the time at which theyare processed, which minimizes the total penalty incurred due to tardiness orearliness of the jobs. This work presents exact polynomial algorithms foroptimizing a given job sequence or single and parallel machines with therun-time complexities of $O(n \log n)$ and $O(mn^2 \log n)$ respectively, where$n$ is the number of jobs and $m$ the number of machines. The algorithms take asequence consisting of all the jobs $(J_i, i=1,2,\dots,n)$ as input anddistribute the jobs to machines (for $m>1$) along with their best completiontimes so as to get the least possible total penalty for this sequence. We provethe optimality for the single machine case and the runtime complexities ofboth. Henceforth, we present the results for the benchmark instances andcompare with previous work for single and parallel machine cases, up to $200$jobs.

Common Due-Date Problem: Exact Polynomial Algorithms for a Given Job Sequence