{"entities":{"Q1717817":{"pageid":1728558,"ns":120,"title":"Item:Q1717817","lastrevid":73817157,"modified":"2026-04-14T17:21:55Z","type":"item","id":"Q1717817","labels":{"en":{"language":"en","value":"Scheduling simple linear deteriorating jobs with rejection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7015835"}},"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":"Q1717817$A1D5EE35-0A49-478B-B17E-E612A5522CCC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b66de1c58978096ad285d81b2d5bdd9bf86691b","datavalue":{"value":{"text":"Scheduling simple linear deteriorating jobs with rejection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1717817$FF784BF8-622E-4992-92A1-354B989AFEB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c0b9088905979261ca611319624aa7890044c31","datavalue":{"value":"1407.90192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$62A16428-82E1-4355-B577-37A8A84733A0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c7a530164a9f785060a1a7cad71abd138f9dfc6","datavalue":{"value":"10.1155/2014/170475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$FBF5AD63-AB40-4771-BA08-1F8B2252D471","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"003ba1617159c82941fa66dc6ec9a0cb927aff9f","datavalue":{"value":{"entity-type":"item","numeric-id":384193,"id":"Q384193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$E1A9721D-FDFE-4DE7-885B-67BD40EFC6BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15dd0018ac59f3b22411758ee094f38fe0d273ac","datavalue":{"value":{"entity-type":"item","numeric-id":402365,"id":"Q402365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$1D0AB2BA-E1C7-4FE0-AD4F-DC03EE08E30B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$662DAB69-71E5-410C-84D0-BE17539035F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32a6dc046c0aa99508538df457dbadf7aa620337","datavalue":{"value":{"time":"+2019-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1717817$BD2E682F-F3FD-4905-A652-0FE17B0FA3FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d95fd603fca0d8f8870ce23e701236d7cb2c42dc","datavalue":{"value":"Summary: We consider the problems of scheduling deteriorating jobs with release dates on a single machine (parallel machines) and jobs can be rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. For a single machine model, the objective is to minimize the maximum lateness of the accepted jobs plus the total penalty of the rejected jobs. We show that the problem is NP-hard in the strong sense and presents a fully polynomial time approximation scheme to solve it when all jobs have agreeable release dates and due dates. For parallel-machine model, the objective is to minimize the maximum delivery completion time of the accepted jobs plus the total penalty of the rejected jobs. When the jobs have identical release dates, we first propose a fully polynomial time approximation scheme to solve it. Then, we present a heuristic algorithm for the case where all jobs have to be accepted and evaluate its efficiency by computational experiments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1717817$A76F3A6B-6C46-4222-BD45-66168BFB6999","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$5AD0936C-D33B-4920-A9B7-F9BE993BFF51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c054e9b88871de547f6e4b3dda9a1dfd1aeb5e92","datavalue":{"value":"7015835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$2CD4980B-A1BB-463D-924C-FE9FFFA47760","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8ab349270c69949fbd9d4aefb523eed58f05a24a","datavalue":{"value":"Q59063447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$53211EDA-4D26-41B6-9D71-2402FD1B3F6F","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":"Q1717817$F61D2269-D535-4711-96A8-6D50D604F010","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82204fbe946d1bcc1a6011da73ea77adca677f2b","datavalue":{"value":"https://doi.org/10.1155/2014/170475","type":"string"},"datatype":"url"},"type":"statement","id":"Q1717817$6A36F40B-386A-4FDC-B613-18F16A729E3D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a92b7b04804c8aa8667f92b4cc21f904aa388680","datavalue":{"value":"W2112080171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1717817$62179BC6-7317-4852-9614-27E636EB5ECA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c86ace6b4e4f5fe9a95a30477aac9736fddaa28","datavalue":{"value":{"entity-type":"item","numeric-id":3483073,"id":"Q3483073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$FE49B627-577A-4D60-8361-79100328AC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3d49306fad4bc798a7bf4687fd676fd838e56ed","datavalue":{"value":{"entity-type":"item","numeric-id":1332800,"id":"Q1332800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$D3462384-1F2B-48C0-8C78-C1B232D43245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"203fd5a37cfa40b066de3fe7562f955b92676e80","datavalue":{"value":{"entity-type":"item","numeric-id":3157377,"id":"Q3157377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$6F002F0A-AAD0-471B-97DE-70BCAFC3FA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0510052fb475c32170b04f7b29cf61e24d4d5dfe","datavalue":{"value":{"entity-type":"item","numeric-id":1410319,"id":"Q1410319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$D86996BC-CCEE-4301-BE13-54BD52EFB7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a5d459d3fc2f34c2b38a3b680e494aa1e6625ec","datavalue":{"value":{"entity-type":"item","numeric-id":1667852,"id":"Q1667852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$929DF05C-33AF-43BE-BA9C-33DA17E7784C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a5110b38aa6b87df229ff18b80719a16fd825ac","datavalue":{"value":{"entity-type":"item","numeric-id":690456,"id":"Q690456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$D3C63F33-6F0B-4B17-96F1-EDE049F0159B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23a7983b4ce7864e454f1782b1ee70600051a858","datavalue":{"value":{"entity-type":"item","numeric-id":2453274,"id":"Q2453274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$24CB219E-F615-4D0A-9109-7484EEB2A0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac783a875a957c8817d93a18fc9982b7ce7f5d71","datavalue":{"value":{"entity-type":"item","numeric-id":4943705,"id":"Q4943705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$C90B8B5C-E1A0-4D61-84FF-7F0A33CE449A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8956315ea27879c61de546884fd6886871e7f3","datavalue":{"value":{"entity-type":"item","numeric-id":1411622,"id":"Q1411622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$0BE57C7E-E938-46BE-8885-D109AB037379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0561ab55324b4a06960a4ab69b2430f4a21de36c","datavalue":{"value":{"entity-type":"item","numeric-id":1042081,"id":"Q1042081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$1D79A7E3-D606-48D7-A9B9-17D33E8AD0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e2ff62435c5e051aa90583f74691076bac9958","datavalue":{"value":{"entity-type":"item","numeric-id":5900744,"id":"Q5900744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$5C4DA9B5-672A-4F5D-9F7F-2A643058C3D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d194232d075409daf0d9f81e4b6c2750b84f522a","datavalue":{"value":{"entity-type":"item","numeric-id":398830,"id":"Q398830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$BAEAF586-A975-436E-B74C-8314D0533622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"556e7f4361e83e7f22a4cf68c77af3c69a2a4605","datavalue":{"value":{"entity-type":"item","numeric-id":953419,"id":"Q953419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$680D3FC2-4E17-4081-902F-CC4E47A3FEA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"781d3509bba81dd219eea929c8c0915764075ac5","datavalue":{"value":{"entity-type":"item","numeric-id":708217,"id":"Q708217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$CE07CCD8-EE71-40DC-9E9E-49EE9A794D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$7F6C806F-B1B7-4F4B-8C6F-F58CE0141071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$36BA1246-91C5-4DE6-9CF2-BDD817A157EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc862222d6d6fc145822303945725d33af59d97","datavalue":{"value":{"entity-type":"item","numeric-id":4820909,"id":"Q4820909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$529DF14F-E174-4E69-AC0D-B9DE750B0C1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9ef75058935aaa5fda156cdc9276b714a65e22b","datavalue":{"value":{"entity-type":"item","numeric-id":4233364,"id":"Q4233364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$DBEA1077-38F7-4771-9734-8499D8C453C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a1f4656d823271b9d9d48df820049ca3365e536","datavalue":{"value":{"entity-type":"item","numeric-id":953419,"id":"Q953419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0ffc68495aa75209f2c43d0291e4657b0ab5973","datavalue":{"value":{"amount":"+0.9518275260925292","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":"Q1717817$77E592D9-85D1-4463-B6D9-BE10902B6A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f1c7b3c31cfa581891b6979bd0f89777b9b5b8","datavalue":{"value":{"entity-type":"item","numeric-id":3166735,"id":"Q3166735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9442f2e635301125bb6949cbd4c7954bf501fd6","datavalue":{"value":{"amount":"+0.9362718462944032","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":"Q1717817$77E0AE87-152E-4313-AA3F-110860E4A4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a447b4c0a4d7b3ff63b48c36f76c908738390824","datavalue":{"value":{"entity-type":"item","numeric-id":708217,"id":"Q708217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9043d84ba4502056e0b43dfd9294d52a743e4e88","datavalue":{"value":{"amount":"+0.9320339560508728","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":"Q1717817$350A6AF6-1C54-4949-AA35-CB91688054DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7f98d04b2ed99bafae610c26dd937b06b12710a","datavalue":{"value":{"entity-type":"item","numeric-id":2923711,"id":"Q2923711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"954d30b9dfa575fb0709b855b6f18181b83c1078","datavalue":{"value":{"amount":"+0.9241527318954468","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":"Q1717817$D0FA7D91-D120-4B97-9D97-9ED6A3F0D0DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4841f8c5bcfa49aefef0a5f94ab510b922d77e43","datavalue":{"value":{"entity-type":"item","numeric-id":2992616,"id":"Q2992616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9e332e616b59b096919ccb3dcc0cf5e5b48cb74","datavalue":{"value":{"amount":"+0.9169009327888488","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":"Q1717817$24568114-6950-4AE5-941B-D7F3BD6C9015","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"daf5f856a5d861312ad309ab567540337a5f61d6","datavalue":{"value":{"entity-type":"item","numeric-id":57050,"id":"Q57050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1717817$F912C455-8232-4027-BD73-073C95582588","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling simple linear deteriorating jobs with rejection","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_simple_linear_deteriorating_jobs_with_rejection"}}}}}