This paper considers the problem of scheduling jobs on single and parallel machines where all the jobs possess different processing times but a common due date. There is a penalty involved with each job if it is processed earlier or later than the due date. The objective of the problem is to find the assignment of jobs to machines, the processing sequence of jobs and the time at which they are processed, which minimizes the total penalty incurred due to tardiness or earliness of the jobs. This work presents exact polynomial algorithms for optimizing a given job sequence or single and parallel machines with the run-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 a sequence consisting of all the jobs $(J_i, i=1,2,\dots,n)$ as input and distribute the jobs to machines (for $m>1$) along with their best completion times so as to get the least possible total penalty for this sequence. We prove the optimality for the single machine case and the runtime complexities of both. Henceforth, we present the results for the benchmark instances and compare with previous work for single and parallel machine cases, up to $200$ jobs.

Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected by a graph structure as communication topology. Each island periodically communicates copies of good solutions to neighboring islands in a process called migration. We consider the speedup gained by island models in terms of the parallel running time for problems from combinatorial optimization: sorting (as maximization of sortedness), shortest paths, and Eulerian cycles. Different search operators are considered. The results show in which settings and up to what degree evolutionary algorithms can be parallelized efficiently. Along the way, we also investigate how island models deal with plateaus. In particular, we show that natural settings lead to exponential vs. logarithmic speedups, depending on the frequency of migration.