×

Minimizing the sum of weighted completion times in a concurrent open shop. (English) Zbl 1202.90139

Summary: We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than \(6/5\) if P \(\neq \) NP, or strictly less than \(4/3\) if the Unique Games Conjecture also holds.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi, R. H.; Bagchi, U., Scheduling of multi-job customer orders in multi-machine environments (1990), ORSA/TIMS: ORSA/TIMS Philadelphia
[2] Ahmadi, R. H.; Bagchi, U.; Roemer, T., Coordinated scheduling of customer orders for quick response, Naval Research Logistics, 52, 493-512 (2005) · Zbl 1122.90034
[3] N. Bansal, S. Khot, Inapproximability of hypergraph vertex cover and applications to scheduling problems, Working paper, 2009.; N. Bansal, S. Khot, Inapproximability of hypergraph vertex cover and applications to scheduling problems, Working paper, 2009. · Zbl 1287.90018
[4] Z.-L. Chen, N.G. Hall, Supply chain scheduling: assembly systems, working paper, Department of Systems Engineering, University of Pennsylvania, 2001.; Z.-L. Chen, N.G. Hall, Supply chain scheduling: assembly systems, working paper, Department of Systems Engineering, University of Pennsylvania, 2001.
[5] Dinur, I.; Guruswami, V.; Khot, S.; Regev, O., A new multilayered PCP and the hardness of hypergraph vertex cover, SIAM Journal on Computing, 34, 1129-1146 (2005) · Zbl 1079.68039
[6] Garg, N.; Kumar, A.; Pandit, V., Order scheduling models: hardness and algorithms, (Arvind, V.; Prasad, S., Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007. Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007, Lecture Notes in Computer Science, vol. 4855 (2007), Springer: Springer Berlin), 96-107 · Zbl 1135.90345
[7] Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 513-544 (1997) · Zbl 0883.90064
[8] J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Management Science Research Project Research Report 43, University of California, Los Angeles, 1955.; J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Management Science Research Project Research Report 43, University of California, Los Angeles, 1955.
[9] S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC 2002, 2002, pp. 767-775.; S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC 2002, 2002, pp. 767-775. · Zbl 1192.68367
[10] Khot, S.; Regev, O., Vertex cover might be hard to approximate within \(2 - \varepsilon \), Journal of Computer and System Sciences, 74, 335-349 (2008) · Zbl 1133.68061
[11] A. Kumar, R. Manokaran, M. Tulsiani, N.K. Vishnoi, On LP-based approximability for strict CSPs, Working paper, 2010.; A. Kumar, R. Manokaran, M. Tulsiani, N.K. Vishnoi, On LP-based approximability for strict CSPs, Working paper, 2010. · Zbl 1377.90077
[12] Leung, J. Y.-T.; Li, H.; Pinedo, M. L., Order scheduling in an environment with dedicated resources in parallel, Journal of Scheduling, 8, 355-386 (2005) · Zbl 1123.90030
[13] Leung, J. Y.-T.; Li, H.; Pinedo, M., Scheduling orders for multiple product types to minimize total weighted completion time, Discrete Applied Mathematics, 155, 945-970 (2007) · Zbl 1113.90060
[14] Queyranne, M., Structure of a simple scheduling polyhedron, Mathematical Programming, 58, 263-285 (1993) · Zbl 0778.90031
[15] M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling, Working paper, 2004.; M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling, Working paper, 2004.
[16] Roemer, T. A., A note on the complexity of the concurrent open shop problem, Journal of Scheduling, 9, 389-396 (2006) · Zbl 1154.90484
[17] Schulz, A. S., Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds, (Cunningham, W. H.; McCormick, S. T.; Queyranne, M., Integer Programming and Combinatorial Optimization, IPCO 1996. Integer Programming and Combinatorial Optimization, IPCO 1996, Lecture Notes in Computer Science, vol. 1084 (1996), Springer: Springer Berlin), 301-315 · Zbl 1414.90167
[18] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[19] Sung, C. S.; Yoon, S. H., Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines, International Journal of Production Economics, 54, 247-255 (1998)
[20] Wagneur, E.; Sriskandarajah, C., Open shops with jobs overlap, European Journal of Operational Research, 71, 366-378 (1993) · Zbl 0797.90047
[21] G. Wang, T.C.E. Cheng, Customer order scheduling to minimize total weighted completion time, in: Proceedings of the First Multidisciplinary Conference on Scheduling Theory and Applications, 2003, pp. 409-416.; G. Wang, T.C.E. Cheng, Customer order scheduling to minimize total weighted completion time, in: Proceedings of the First Multidisciplinary Conference on Scheduling Theory and Applications, 2003, pp. 409-416.
[22] Wolsey, L. A., Mixed integer programming formulations for production planning and scheduling problems, (Invited Talk at the 12th International Symposium on Mathematical Programming (1985), MIT: MIT Cambridge, MA)
[23] J. Yang, Scheduling with batch objectives, Ph.D. Thesis, Industrial and Systems Engineering, The Ohio State University, 1998.; J. Yang, Scheduling with batch objectives, Ph.D. Thesis, Industrial and Systems Engineering, The Ohio State University, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.