{"entities":{"Q1208472":{"pageid":1219221,"ns":120,"title":"Item:Q1208472","lastrevid":47149162,"modified":"2025-12-31T20:24:05Z","type":"item","id":"Q1208472","labels":{"en":{"language":"en","value":"On polynomial solvability of the high multiplicity total weighted tardiness problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166469"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$456A6E2B-F1E0-4553-9809-A19B038A2E68","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66e5ec5c07eff8abfd6c7f7585cb49b829903751","datavalue":{"value":{"text":"On polynomial solvability of the high multiplicity total weighted tardiness problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208472$6303A0D0-BC1A-4125-8C44-238E5EA24D54","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"deb6ce9ca8ef5ab8b362f480baf2b33df92de03d","datavalue":{"value":"0779.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$37A5E489-9BBA-4E84-AE82-D36EB072BA41","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"116a0df73bc5e773ac505d6ca8e6d69e429ddb1d","datavalue":{"value":"10.1016/0166-218X(93)90034-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$FBE5C288-759F-4C9C-9BD3-48235B1780FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cce947c11bd7fd58c83190d519ef228f357b0b1f","datavalue":{"value":{"entity-type":"item","numeric-id":233532,"id":"Q233532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$323CCA27-53FB-48C8-9FFF-F7A58FC4CE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ed74cd8b4711628a611438aeb686bfc6e5f9f03","datavalue":{"value":{"entity-type":"item","numeric-id":751507,"id":"Q751507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$E390F7E9-D086-463C-B244-9E49DA270854","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$5428B00E-6BFF-466E-B4A5-4C434DAEDE4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208472$520A5EF3-0EC0-4EC6-B0E8-4E71D6207981","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86458d33ffa6991dccdd364e9730411ed46a05ea","datavalue":{"value":"The following scheduling problem is addressed in the paper. Many jobs of unit length but with only a few sets of distinct due dates and penalty weights need to be sequenced on a single machine. The objective is to minimize the total weighted tardiness. Recently, \\textit{D. S. Hochbaum}, \\textit{R. Shamir} and \\textit{J. G. Shantikumar} [Math. Program. 55A, No. 3, 359-371 (1992; Zbl 0761.90061)] formulated this problem as an integer quadratic nonseparable transportation problem. In the paper under review the authors transform the total weighted tardiness problem to an equivalent separable problem with totally unimodular constraint matrix. The latter can be solved in time polynomial in the dimension of the problem and only the size of the maximal difference between two consecutive due dates. In the case where the due dates are large but the size of the maximal difference between two consecutive due dates is polynomially bounded by the dimension of the problem, the algorithm runs in strongly polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208472$8D81854F-FAC9-4B8C-B3C5-E36C16F2DB84","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$F7761AE2-21C2-4190-8DA7-38D357E6BE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$FEA010D0-86C5-4951-9447-F5D9953D08D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$C3ABF60F-28CA-4030-92FC-BC28E4FFAB4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$1FB37F75-BC0E-44D2-8642-94AB19E7C3E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34c37dec2ddcd09038bd401e3d48765515c3532e","datavalue":{"value":"166469","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$717F0CA5-D401-442C-BFF6-5F146F9153F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1ca53a04f8c624238a62137bcb0acb8058cd7ee","datavalue":{"value":"single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208472$C3416D6F-FD28-4DF8-9F23-36A005BB8584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5297cc836fdeea4f8982415ef53230d67625fcd9","datavalue":{"value":"total weighted tardiness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208472$51A11B9C-8609-4F4F-83DC-34455AEA2793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8de9c754a7b4c176fe5943dd48f2cc45e99f6342","datavalue":{"value":"integer quadratic nonseparable transportation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208472$9590959A-BB62-485A-AE77-6D9AAFEE178B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$D4F5C47B-930E-4218-84FC-44B576B10E4A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$C4CCF5E9-49EA-4E89-A0E8-D10B41CE54CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfd23612b2bb80c88a940c6564bf3b173563250d","datavalue":{"value":{"entity-type":"item","numeric-id":1088911,"id":"Q1088911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$43F68A84-5645-4A36-9625-47A6426DF115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbb1a41e1372e3162132a743fdeb824a6c86760e","datavalue":{"value":{"entity-type":"item","numeric-id":2314408,"id":"Q2314408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$DB6B741D-9393-4826-93F7-5F5FE57F0F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daae7e23365b60fd68b4bbe0dd0bb7eb66daf158","datavalue":{"value":{"entity-type":"item","numeric-id":909582,"id":"Q909582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$D81E1D25-7062-4FC6-A48B-5D90DC38CBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb512aecde3c8e85d69222af66dfcd0755f36100","datavalue":{"value":{"entity-type":"item","numeric-id":1198737,"id":"Q1198737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$BD6287CF-91A1-409B-8DE9-E73CA57DB8FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dba761686c2eb74a4af9736c7d5a8d52e5c5c8a0","datavalue":{"value":{"entity-type":"item","numeric-id":5753748,"id":"Q5753748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$6E1273D8-ADDD-41F1-B1BF-440912AF30E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$DE71F6F6-6C5D-4DAE-B4D2-D6414DF94853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aea04970626c2b6a6205a53b4ddfbe1134bb9c2","datavalue":{"value":{"entity-type":"item","numeric-id":3030579,"id":"Q3030579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208472$D05236CC-918C-4A58-8A74-39D4754EE8E1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1a65b1aa92e0f6c742e4b11a544dc0fd63dface","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90034-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q1208472$74463A70-D1B3-4872-9114-75F2FA1ABC8F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba1204758825a1770dce51450b633b9549aa37b5","datavalue":{"value":"W1975401191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208472$FD9D8FF0-C259-415D-93DC-050FCE9AA108","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"451560dfb2d9726dfaf1a427caf5c30956316327","datavalue":{"value":{"entity-type":"item","numeric-id":1198737,"id":"Q1198737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba4b9556055ad0c4bc5480dd0961b84b62543f33","datavalue":{"value":{"amount":"+0.8463687896728516","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1208472$4FF90B38-054A-4883-B984-E3A2B2F32CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78abe2e9bf7e86e62cbe0ddd2804270bb6bb1ac2","datavalue":{"value":{"entity-type":"item","numeric-id":5309698,"id":"Q5309698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d74a8377f58df9219560d8fa62ea0f5bd8babbe7","datavalue":{"value":{"amount":"+0.8452833294868469","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1208472$87187C98-550B-4D69-8D6E-306FB74A2D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e488d4535d43bb4468e26ffa3372a20749a088f","datavalue":{"value":{"entity-type":"item","numeric-id":3980518,"id":"Q3980518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e94e01cd19f93f2885b36fcdecdc9f55550efcb","datavalue":{"value":{"amount":"+0.8406327962875366","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1208472$3F47905B-435F-40EC-BFE0-CD6171AA801C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89f4978118837a1774ad75d907d99993d0b93550","datavalue":{"value":{"entity-type":"item","numeric-id":2368997,"id":"Q2368997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20d0e74201f5765af3f385139d95c31b155c2c60","datavalue":{"value":{"amount":"+0.839931070804596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1208472$3BE2AA5D-154E-42DF-8798-285C30BEE989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"190714331dc055d670a41fca339e2b8deee5a032","datavalue":{"value":{"entity-type":"item","numeric-id":1772846,"id":"Q1772846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1d7891759864ce43aeb54a8c75f7e7217fe7a61","datavalue":{"value":{"amount":"+0.8394293785095215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1208472$CCF9C684-A6A3-4AE2-ABC5-9BF7A8603F11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1208472","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1208472"}}}}}