{"entities":{"Q1178528":{"pageid":1189277,"ns":120,"title":"Item:Q1178528","lastrevid":67043694,"modified":"2026-04-12T14:31:41Z","type":"item","id":"Q1178528","labels":{"en":{"language":"en","value":"Single machine scheduling problem with a common deadline and resource dependent release dates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 21799"}},"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":"Q1178528$98C1A29A-C00B-4490-BA35-2A398F27283E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe405b13ca22825ae47aa916a4d8534fc343a3a7","datavalue":{"value":{"text":"Single machine scheduling problem with a common deadline and resource dependent release dates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178528$07DC1483-88F7-468C-93C7-BD886DFE6662","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f562b4e4517801223f2c25bb48012f4bfc31fec2","datavalue":{"value":"0743.90066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$80EB7985-3CA9-4D23-B159-2449EADDCD81","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77d99358fde30b990e5d8052f37383f144cdfb59","datavalue":{"value":"10.1016/0377-2217(91)90065-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$3A02777D-ECB9-44CD-A6F7-E810D4FAD6DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4614217cf884394cbf40084cf1694a9b93ee2163","datavalue":{"value":{"entity-type":"item","numeric-id":168279,"id":"Q168279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$75421467-5E53-4DCD-BC31-4EBAD0EED96F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$5F24BD20-2E55-4520-810D-E47E21E25C40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178528$8F86EF75-4652-442C-8948-1C06A5005328","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c71c2d9e004909c0b2fe44571dd798cf02206b1","datavalue":{"value":"We have \\(n\\) independent jobs which can be performed in a single machine so that each job runs in a non-interruptable time interval of length \\(b_ i\\), which is disjoint from the same interval of other jobs. Each job has a different availability time \\(t_ i\\) at the start. The jobs demand \\(r_ i\\) amounts of resource, and the \\(i\\)-th job must satisfy the following condition: \\(t_ i=b_ i-a_ ir_ i\\). The paper deals with the problem of minimizing the sum of used resources in a limited total schedule time. NP-completeness is proved in general, but approximate algorithms are given for some special cases. Some numerical examples were also tested.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178528$9D691510-9466-4DCE-830C-96338E1D7023","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$7E8335B4-C362-44EB-AFFA-B5AAB0666D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$98E1FBCA-DE12-445B-9FEF-5348E6CA53EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39dc79e430cd8a60522a6f1a7af0d618da293b81","datavalue":{"value":"21799","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$BE2AB4B2-6C51-495B-A5C2-0A9EB610A5A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72beada0adab827b7d0d91c10d5c266ab10e7bcd","datavalue":{"value":"resource dependent release dates","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178528$8DE16F7D-FB09-4596-88AF-03C0D005CD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50ef05c6d830193e071c5ee114522736b6178603","datavalue":{"value":"common deadline","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178528$08F70B6B-245B-49D2-A6F7-A0513A5DB1B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1ca53a04f8c624238a62137bcb0acb8058cd7ee","datavalue":{"value":"single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178528$7A3ED0CA-F769-4022-B1D5-15962A6E17C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b037e835bec10946c8275121512d8f5f0a03729","datavalue":{"value":"approximate algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178528$C1DE1007-161B-4A11-A5FA-F618262669AA","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":"Q1178528$4BC3D28F-32DE-43F6-AD26-C4285D1B03E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2cfb0ac87f5f7c8434224d8ee5f993a3189380e","datavalue":{"value":"https://doi.org/10.1016/0377-2217(91)90065-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178528$77E2B908-EFCE-4467-9534-680363EDD8AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"41560229cf7f6b07ed43785772c8ddc6d2478e54","datavalue":{"value":"W1977185976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178528$4FADA8E6-AA1D-4321-ADBE-6551B4979253","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b153e6a92a65a41501aa0a1819873f5d9ce7b9d9","datavalue":{"value":{"entity-type":"item","numeric-id":3200872,"id":"Q3200872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$37599CEE-0213-482F-BB17-50978ED15AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b635f06f6c39b03ca513d0a3eb06ec0cc20b065","datavalue":{"value":{"entity-type":"item","numeric-id":1820680,"id":"Q1820680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$99C72D0F-5B6D-445F-9F91-A128564DE870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9c559c1a518e4b54e316e3af40a0ae10614fbf7","datavalue":{"value":{"entity-type":"item","numeric-id":1086143,"id":"Q1086143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$251AC470-FA8D-4E63-B681-8D9BD0511CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"367946ffe1ff1ae48a43f0047acab4605713faf5","datavalue":{"value":{"entity-type":"item","numeric-id":3780743,"id":"Q3780743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$F85EBA57-821B-4DDB-BB41-87E97376F6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f7554ce785ccaf16d476f70c26809213d91df9","datavalue":{"value":{"entity-type":"item","numeric-id":3775317,"id":"Q3775317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$39FC3F21-6133-4F76-A508-1B6FE04BDE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a54363cab19ddaa83ba50c46c8127b159b14d03","datavalue":{"value":{"entity-type":"item","numeric-id":4055377,"id":"Q4055377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178528$DBD2A1FB-96B7-4B72-AD36-62986EBF5071","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf0d73a49480717df0314850964b7622e548f1a6","datavalue":{"value":{"entity-type":"item","numeric-id":1278308,"id":"Q1278308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e9e559c885119c1a4a9013e34722e43fd28b638","datavalue":{"value":{"amount":"+0.8909885883331299","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":"Q1178528$50D68DB3-28F6-42B9-BB6A-724C85425145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b40a9ae3af8fd770018b89ccff81df56393e3a3","datavalue":{"value":{"entity-type":"item","numeric-id":868136,"id":"Q868136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44d400ba8a420bf2ac9a6b921d28963f84caf26f","datavalue":{"value":{"amount":"+0.875467836856842","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":"Q1178528$D3B0B554-0AC9-49D7-876C-C08834D4A59E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d86a9c80fa2ee064012463a560120a61d5d3fa5","datavalue":{"value":{"entity-type":"item","numeric-id":704120,"id":"Q704120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dd12da4cf887f268f69629d5225060bea6b11ee","datavalue":{"value":{"amount":"+0.8619310855865479","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":"Q1178528$8B2618C3-DFFB-4E8D-98E2-4CD5BD58588D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63199f8981a8243b1ecea1e40655dc8b5f070157","datavalue":{"value":{"entity-type":"item","numeric-id":4314866,"id":"Q4314866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c06bf6b39da9feef3e3afc68caa4121950612937","datavalue":{"value":{"amount":"+0.8563554286956787","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":"Q1178528$928908DD-5903-4E4F-953F-FD99CCB9D97E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Single machine scheduling problem with a common deadline and resource dependent release dates","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Single_machine_scheduling_problem_with_a_common_deadline_and_resource_dependent_release_dates"}}}}}