{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:36:14Z","timestamp":1759847774624},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01585568","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:17Z","timestamp":1114677737000},"page":"413-428","source":"Crossref","is-referenced-by-count":9,"title":["Dual decomposition of a single-machine scheduling problem"],"prefix":"10.1007","volume":"69","author":[{"given":"S. L.","family":"van de Velde","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D. Adolphson","year":"1973","unstructured":"D. Adolphson and T.C. Hu, \u201cOptimal linear ordering,\u201dSIAM Journal of Applied Mathematics 25 (1973) 403\u2013423.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584228","volume":"21","author":"E. Balas","year":"1981","unstructured":"E. Balas and N. Christofides, \u201cA restricted Lagrangean approach to the traveling salesman problem,\u201dMathematical Programming 21 (1981) 19\u201346.","journal-title":"Mathematical Programming"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0167-5060(08)70728-3","volume":"1","author":"O. Bilde","year":"1977","unstructured":"O. Bilde and S. Krarup, \u201cSharp lower bounds and efficient algorithms for the simple plant location problem,\u201dAnnals of Discrete Mathematics 1 (1977) 79\u201388.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1137\/0119070","volume":"19","author":"N. Christofides","year":"1970","unstructured":"N. Christofides, \u201cThe shortest hamiltonian chain of a graph,\u201dSIAM Journal of Applied Mathematics 19 (1970) 689\u2013696.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M.E. Dyer","year":"1990","unstructured":"M.E. Dyer and L.A. Wolsey, \u201cFormulating the single-machine sequencing problem with release dates as a mixed integer program,\u201dDiscrete Applied Mathematics 26 (1990) 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"key":"CR6","first-page":"1114","volume":"21","author":"D. Erlenkotter","year":"1978","unstructured":"D. Erlenkotter, \u201cA dual-based procedure for uncapacitated facility location,\u201dOperations Research 21 (1978) 1114\u20131127.","journal-title":"Operations Research"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01580393","volume":"11","author":"M.L. Fisher","year":"1976","unstructured":"M.L. Fisher, \u201cA dual algorithm for the one-machine scheduling problem,\u201dMathematical Programming 11 (1976) 229\u2013251.","journal-title":"Mathematical Programming"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"M.L. Fisher","year":"1981","unstructured":"M.L. Fisher, \u201cThe Lagrangian relaxation method for solving integer programming problems,\u201dManagement Science 27 (1981) 1\u201318.","journal-title":"Management Science"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1287\/inte.15.2.10","volume":"15","author":"M.L. Fisher","year":"1985","unstructured":"M.L. Fisher, \u201cAn application oriented guide to Lagrangian relaxation,\u201dInterfaces 15 (1985) 10\u201321.","journal-title":"Interfaces"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1287\/mnsc.32.9.1095","volume":"32","author":"M.L. Fisher","year":"1986","unstructured":"M.L. Fisher, R. Jaikumar and L.N. van Wassenhove, \u201cA multiplier adjustment method for the generalized assignment problem,\u201dManagement Science 32 (1986) 1098\u20131103.","journal-title":"Management Science"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1287\/mnsc.36.6.674","volume":"36","author":"M.L. Fisher","year":"1990","unstructured":"M.L. Fisher and P. Kedia, \u201cOptimal solution of set covering\/partitioning problems using dual heuristics,\u201dManagement Science 36 (1990) 674\u2013688.","journal-title":"Management Science"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A.M. Geoffrion","year":"1974","unstructured":"A.M. Geoffrion, \u201cLagrangian relaxation and its uses in integer programming,\u201dMathematical Programming Study 2 (1974) 82\u2013114.","journal-title":"Mathematical Programming Study"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, \u201cOptimization and approximation in deterministic sequencing and scheduling: a survey,\u201dAnnals of Discrete Mathematics 5 (1979) 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BF01588244","volume":"17","author":"M. Guignard","year":"1979","unstructured":"M. Guignard and K. Spielberg, \u201cA direct dual method of the mixed plant location problem with some side constraints,\u201dMathematical Programming 17 (1979) 198\u2013228.","journal-title":"Mathematical Programming"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0166-218X(83)90019-7","volume":"5","author":"A.M.A. Hariri","year":"1983","unstructured":"A.M.A. Hariri and C.N. Potts, \u201cAn algorithm for single-machine sequencing with release dates to minimize total weighted completion time,\u201dDiscrete Applied Mathematics 5 (1983) 99\u2013109.","journal-title":"Discrete Applied Mathematics"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/0377-2217(84)90238-8","volume":"17","author":"A.M.A. Hariri","year":"1984","unstructured":"A.M.A. Hariri and C.N. Potts, \u201cAlgorithms for two-machine flow-shop sequencing with precedence constraints,\u201dEuropean Journal of Operational Research 17 (1984) 238\u2013248.","journal-title":"European Journal of Operational Research"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R.M. Karp, \u201cThe traveling salesman problem and minimum spanning trees,\u201dOperations Research 18 (1970) 1138\u20131162.","journal-title":"Operations Research"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R.M. Karp, \u201cThe traveling salesman problem and minimum spanning trees: Part II,\u201dMathematical Programming 1 (1971) 6\u201325.","journal-title":"Mathematical Programming"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe and H. Crowder, \u201cValidation of subgradient optimization,\u201dMathematical Programming 6 (1974) 62\u201388.","journal-title":"Mathematical Programming"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"J.A. Hoogeveen and S.L. van de Velde, \u201cStronger Lagrangian bounds by use of slack variables: applications to machine scheduling problems,\u201dMathematical Programming 70 (1995), to appear.","DOI":"10.1007\/BF01585935"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/0123021","volume":"23","author":"W.A. Horn","year":"1972","unstructured":"W.A. Horn, \u201cSingle-machine job sequencing with treelike precedence ordering and linear delay penalties,\u201dSIAM Journal of Applied Mathematics 23 (1972) 189\u2013202.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E.L. Lawler","year":"1978","unstructured":"E.L. Lawler, \u201cSequencing jobs to minimize total weighted completion time subject to precedence constraints,\u201dAnnals of Discrete Mathematics 2 (1978) 75\u201390.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR23","volume-title":"\u201cEfficient implementation of dynamic programming algorithms for sequencing problems,\u201d Report BW 106","author":"E.L. Lawler","year":"1979","unstructured":"E.L. Lawler, \u201cEfficient implementation of dynamic programming algorithms for sequencing problems,\u201d Report BW 106, Centre for Mathematics and Computer Science (Amsterdam, 1979)."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"J.K. Lenstra and A.H.G. Rinnooy Kan, \u201cComplexity of scheduling under precedence constraints,\u201dOperations Research 26 (1978) 22\u201335.","journal-title":"Operations Research"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1287\/mnsc.24.10.1011","volume":"24","author":"T.E. Morton","year":"1978","unstructured":"T.E. Morton and B.G. Dharan, \u201cAlgoristics for single-machine sequencing with precedence constraints,\u201dManagement Science 24 (1978) 1011\u20131020.","journal-title":"Management Science"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1287\/mnsc.31.10.1300","volume":"31","author":"C.N. Potts","year":"1985","unstructured":"C.N. Potts, \u201cA Lagrangean based branch-and-bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time,\u201dManagement Science 31 (1985) 1300\u20131311.","journal-title":"Management Science"},{"key":"CR27","first-page":"363","volume":"33","author":"C.N. Potts","year":"1983","unstructured":"C.N. Potts and L.N. van Wassenhove, \u201cAn algorithm for single-machine sequencing with deadlines to minimize total weighted completion time,\u201dEuropean Journal of Operational Research 33 (1983) 363\u2013377.","journal-title":"European Journal of Operational Research"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/opre.33.2.363","volume":"33","author":"C.N. Potts","year":"1985","unstructured":"C.N. Potts and L.N. van Wassenhove, \u201cA branch and bound algorithm for the total weighted tardiness problem,\u201dOperations Research 33 (1985) 363\u2013377.","journal-title":"Operations Research"},{"key":"CR29","series-title":"Working paper","volume-title":"Polyhedral approaches to machine scheduling","author":"M. Queyranne","year":"1994","unstructured":"M. Queyranne and A.S. Schulz, \u201cPolyhedral approaches to machine scheduling,\u201d Working paper, Technische Universit\u00e4t Berlin (Berlin, 1994)."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.16.1.1","volume":"16","author":"M. Queyranne","year":"1991","unstructured":"M. Queyranne and Y. Wang, \u201cSingle-machine scheduling polyhedra with precedence constraints,\u201dMathematics of Operations Research 16 (1991) 1\u201320.","journal-title":"Mathematics of Operations Research"},{"key":"CR31","series-title":"Working paper","volume-title":"A cutting plane procedure for precedence constrained single-machine scheduling","author":"M. Queyranne","year":"1991","unstructured":"M. Queyranne and Y. Wang, \u201cA cutting plane procedure for precedence constrained single-machine scheduling,\u201d Working paper, University of British Columbia (Vancouver, 1991)."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1287\/opre.26.3.444","volume":"26","author":"L. Schrage","year":"1978","unstructured":"L. Schrage and K.R. Baker, \u201cDynamic programming solution of sequencing problems with precedence constraints,\u201dOperations Research 26 (1978) 444\u2013449.","journal-title":"Operations Research"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0167-5060(08)70346-7","volume":"5","author":"J.F. Shapiro","year":"1974","unstructured":"J.F. Shapiro, \u201cA survey of Lagrangian techniques for discrete optimization,\u201dAnnals of Discrete Mathematics 5 (1974) 113\u2013138.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"J.B. Sidney","year":"1975","unstructured":"J.B. Sidney, \u201cDecomposition algorithms for single-machine sequencing with predecence relations and deferral costs,\u201dOperations Research 23 (1975) 283\u2013298.","journal-title":"Operations Research"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"W.E. Smith, \u201cVarious optimizers for single-stage production,\u201dNaval Research Logistics Quarterly 3 (1956) 59\u201366.","journal-title":"Naval Research Logistics Quarterly"},{"key":"CR36","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF03500931","volume":"26","author":"S.L. Velde van de","year":"1990","unstructured":"S.L. van de Velde, \u201cMinimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation,\u201dAnnals of Operations Research 26 (1990) 257\u2013268.","journal-title":"Annals of Operations Research"},{"key":"CR37","volume-title":"Machine scheduling and Lagrangian relaxation","author":"S.L. Velde van de","year":"1991","unstructured":"S.L. van de Velde, \u201cMachine scheduling and Lagrangian relaxation,\u201d Ph.D. Thesis, CWI (Amsterdam, 1991)."},{"key":"CR38","volume-title":"Economic Decision-Making: Games, Econometrics and Optimization","author":"L.A. Wolsey","year":"1990","unstructured":"L.A. Wolsey, \u201cFormulating single-machine scheduling polyhedra with precedence constraints,\u201d in: J. Gabszewicsz, J.-F. Richard and L.A. Wolsey, eds.,Economic Decision-Making: Games, Econometrics and Optimization (North-Holland, Amsterdam, 1990)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585568.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585568\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:47:42Z","timestamp":1586231262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":38,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01585568"],"URL":"https:\/\/doi.org\/10.1007\/bf01585568","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}