{"entities":{"Q604766":{"pageid":606542,"ns":120,"title":"Item:Q604766","lastrevid":63041460,"modified":"2026-04-11T09:57:28Z","type":"item","id":"Q604766","labels":{"en":{"language":"en","value":"A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5815545"}},"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":"Q604766$83E07653-3737-4E4B-A7E2-35FFB6DC0C47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a80397789157ff6c2f8c5580c7b0ba7a0e7287e","datavalue":{"value":{"text":"A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q604766$EB671949-17AF-4E07-BF0B-4338BC23FE83","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"248e4a1904c19e4ac9aedb85de68ec73aed7eb04","datavalue":{"value":"1198.90197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$3A137C1E-FD4F-41D5-9955-AACE4D2660A5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"639520293740da0fa2e985102191ba28eb8a3a27","datavalue":{"value":"10.1504/IJOR.2010.034069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$0E5BD7F4-ECBC-4BCD-8271-99AA4ED5D063","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"310f991a9cb18035635398831eb90855d81edfd0","datavalue":{"value":{"entity-type":"item","numeric-id":336391,"id":"Q336391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604766$5FEB3447-ACAF-4872-98C8-C4EA3488E889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"21216cc5ac0d56abae513fea1efa61d34a15a922","datavalue":{"value":{"entity-type":"item","numeric-id":604764,"id":"Q604764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604766$71F4DE60-BF31-4B73-89C7-B5C3733FBC95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9adce6b322a90870165836789491007ae984b03","datavalue":{"value":{"entity-type":"item","numeric-id":604765,"id":"Q604765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604766$6B6B2732-1A31-49EF-AA14-7D0106C63AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b4495a9ada6077999f70e1adbe11a3f7f7129f8","datavalue":{"value":{"entity-type":"item","numeric-id":320112,"id":"Q320112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604766$71A39B48-CACC-43FD-A370-A633BB360F85","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604766$5EC12829-824C-4901-B4ED-9E03D5BCA0BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f9e839d2a997fa299b899aeddb064bd0b055cfd","datavalue":{"value":{"time":"+2010-11-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q604766$CC527C5E-816F-4206-B836-2170B310C965","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3a98d4b77c7cfaec676b02c20fdcae55c4b223b","datavalue":{"value":"Summary: We consider the problem of scheduling \\(n\\) jobs on a single machine to minimise the sum of maximum earliness and tardiness. Since this problem is trying to minimise the earliness and tardiness values, the model is consistent with the just-in-time production system. Most of publications on this subject have studied ``min-sum'' objective functions, but in many settings balancing the costs of the jobs by minimising the cost of the worst scheduled job as ``min-max'' criteria is more important. Using efficient lower and upper bounds and new dominance rules, a branch-and-bound scheme is proposed. The proposed algorithm is then tested on a set of randomly generated problems of different sizes, varying from 5 to 1,000 jobs. Using these approaches, we are able to solve all problems in a reasonable time. Computational results demonstrate the efficiency of our branch-and-bound algorithm over the existing methods reported in the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$D129420A-7D25-43EF-BCC0-5B2DFEFDDED5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$A7A1982D-8117-4DCD-BB4B-DB1BAC3CBF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$10FD49A1-63BA-42EA-BDD2-3B3B0763A62A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70da62a6ea5a8be99439d74f89f05e4932e70d52","datavalue":{"value":"5815545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$5102A0F0-F76A-4F60-BC32-4305258B4026","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0e3d728e919b501eeffb6cfc4b13649fe92461f","datavalue":{"value":"single machine scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$09C91C1A-C745-42E3-AB8E-E0B46CAFE4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41b8226b7f0f6874adaf5ec4de245586221332c3","datavalue":{"value":"earliness","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$0B2737A7-D499-49A6-8D1C-72BEDD542EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53a520b4fbef38a0ac1568aecebfbe5ffd5397ea","datavalue":{"value":"tardiness","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$99B6A574-B7BE-4F12-BD27-E95C8382CC66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$10B7AF43-46EB-4955-AA23-E58CB7F5C3F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f877b4762839bc1a94ce9d9a77c71b5635c84b2","datavalue":{"value":"just-in-time","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$5FFADB9E-685F-4B0D-8AA5-D8CA8AA1170C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40dd8dd65b78f4e6660dcba98121575d9a6aa2ec","datavalue":{"value":"JIT production","type":"string"},"datatype":"string"},"type":"statement","id":"Q604766$5641D2E2-8333-4406-85E0-C21BCD5B4DE9","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":"Q604766$85EEE15E-26CB-4748-AFC5-119658400B96","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ecae71a061066dc7e3c4dd8139184f56cd5a50c","datavalue":{"value":"https://doi.org/10.1504/ijor.2010.034069","type":"string"},"datatype":"url"},"type":"statement","id":"Q604766$85DF23DF-B320-4AA9-B4B6-BC36CF49A48F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9122e8476f4c5a719819225331188eb1e3386497","datavalue":{"value":"W2002220688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604766$4B3CEE59-1FFD-4603-859C-65D628038C45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f49a70344755d49552ac2e9b218397c8454009c3","datavalue":{"value":{"entity-type":"item","numeric-id":1302719,"id":"Q1302719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2707b6619242d250b5fe351868ec3df8f754cfa","datavalue":{"value":{"amount":"+0.9006451964378357","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":"Q604766$1DD387E7-8FC2-4F60-801E-5C6C2EF371DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"818bfec7a655090e39d5c8f0bb6c4202ef1cc39d","datavalue":{"value":{"entity-type":"item","numeric-id":2490218,"id":"Q2490218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aee65451d18c2c7d911fe79dba5cab782125988d","datavalue":{"value":{"amount":"+0.8954214453697205","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":"Q604766$E856D701-AFEA-4B6E-BC33-8FDE440D51D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"522cf0d477eb0acfd078b5d552467e8b43df8d26","datavalue":{"value":{"entity-type":"item","numeric-id":5962398,"id":"Q5962398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e98a94f0bbe3f7d1adac53be67579eb7d2ea159","datavalue":{"value":{"amount":"+0.8815618753433228","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":"Q604766$F73A433D-63B6-4ED8-9201-30E1AF8AC652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"562284a99a03a6b6ea6665401fda557ca1c90e62","datavalue":{"value":{"entity-type":"item","numeric-id":4367055,"id":"Q4367055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0a9536b7cffbec978a4b21942854fb0a5fe6ceb","datavalue":{"value":{"amount":"+0.8779913783073425","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":"Q604766$70B81BEA-B873-4C2B-86F5-8720C0244815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dcef03c472c6d0fc2eceea9e5ca776360d32435","datavalue":{"value":{"entity-type":"item","numeric-id":630678,"id":"Q630678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5f873c656e94a60b3d955d99dfdeb3cd8cce15a","datavalue":{"value":{"amount":"+0.8761388659477234","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":"Q604766$6A3F599F-1B83-4172-B162-470B890B888B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_branch-and-bound_algorithm_to_minimise_the_sum_of_maximum_earliness_and_tardiness_in_the_single_machine"}}}}}