Minimizing the maximum deviation of job completion time about a common due-date (Q1098766)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimizing the maximum deviation of job completion time about a common due-date |
scientific article |
Statements
Minimizing the maximum deviation of job completion time about a common due-date (English)
0 references
1987
0 references
Given a set of n jobs with deterministic processing times and the same ready times, the problem is to find the optimal common due-date \(k^*\) and the optimal job sequences \(\sigma^*\) to minimize the maximum deviation of job completion time about the common due-date. It is shown that the problem can be formulated as an equivalent linear programming (LP) minimization problem. Using the strong duality property of LP, we derive the optimal due-date by considering the dual of the LP problem. When the optimal due-date is determined the optimal job seqa set S. Remember that the pair (S,\(\sigma)\) is called a convexity space if \(\sigma\) is closed under intersections and if S,\(\emptyset \in \sigma\). The authors introduce and discuss the following notion of \(\sigma\)- separability: a set \(X\subset S\) is called to be \(\sigma\)-separable from a set \(Y\subset S\) if there is an \(A\in \sigma\) such that \(X\subset A\subset S\setminus Y.\)
0 references
deterministic processing times
0 references
optimal common due-date
0 references
optimal job sequences
0 references
convexity space
0 references
separability
0 references
0 references