History

Please fill in your query. A complete syntax description you will find on the General Help page.
Non-approximability of just-in-time scheduling. (English)
J. Sched. 12, No. 5, 555-562 (2009).
Summary: We consider the following single machine just-in-time scheduling problem with earliness and tardiness costs: Given $n$ jobs with processing times, due dates and job weights, the task is to schedule these jobs without preemption on a single machine such that the total weighted discrepancy from the given due dates is minimum. NP-hardness of this problem is well established, but no approximation results are known. Using the gap-technique, we show in this paper that the weighted earliness-tardiness scheduling problem and several variants are extremely hard to approximate: If $n$ denotes the number of jobs and $b\in \Bbb N$ is any given constant, then no polynomial-time algorithm can achieve an approximation which is guaranteed to be at most a factor of $O(b^{n})$ worse than the optimal solution unless P $=$ NP. We also present positive results for two special cases. If the individual processing times and likewise the job weights are similar, i.e., they deviate from each other only by a constant factor, then we obtain constant approximation ratios in pseudopolynomial time. For the second special case, we assume only a constant number of distinct due dates. Then we obtain a pseudopolynomial time exact algorithm using an adaption of a dynamic programming approach introduced by {\it S. G. Kolliopoulos} and {\it G. Steiner} [Theor. Comput. Sci. 355, No. 3, 261‒273 (2006; Zbl 1088.68024)] for the total weighted tardiness problem.