{"entities":{"Q1098765":{"pageid":1109517,"ns":120,"title":"Item:Q1098765","lastrevid":49138831,"modified":"2026-01-06T15:59:34Z","type":"item","id":"Q1098765","labels":{"en":{"language":"en","value":"Scheduling jobs with fixed start and end times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037584"}},"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":"Q1098765$06FD1629-C89F-40DD-A160-61E18E60233E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f21331fdab9b1babe81958b479b19fabcf85a173","datavalue":{"value":{"text":"Scheduling jobs with fixed start and end times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098765$FC2D0201-D5B1-439B-8C16-4B4E6E84488C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d76c511ff362f0c5576be23b68cd7b0249f50f7","datavalue":{"value":"0636.90042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098765$BE9FCDB7-2C9E-47CC-ADFD-21BD23817D5A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aff120f541e3713a0519eebf72e710bddd874a70","datavalue":{"value":"10.1016/0166-218X(87)90037-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098765$B11743BC-19D5-4E4F-AD82-3BBF7B5301D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0f96198222aeec1a9630a1398f93a76816f149d","datavalue":{"value":{"entity-type":"item","numeric-id":233538,"id":"Q233538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$87BD85B8-0926-4068-ABDA-DBCE65B31DD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0f614d042ad74dd6b190ef3c93742e33ce48b79d","datavalue":{"value":{"entity-type":"item","numeric-id":1098642,"id":"Q1098642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$26694E13-842D-423C-A778-F97B6C5C9235","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":"Q1098765$E28E83D1-FCBC-410D-B461-263AD3D6CFD2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1098765$E60CC179-D00D-4AB9-9D48-2ED8E3361A14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8c32f8b1bb5638f5ecd6adf2139e5a88cb840f12","datavalue":{"value":"We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time \\(O(n^ 2 \\log n)\\), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction. Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an \\(O(n^{k+1})\\) time algorithm is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$0B332EAF-49F3-4673-BD06-598479444CFF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098765$DAF0003F-C373-4509-990E-CE6E9EBF28E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098765$F6F6F76E-B403-4001-B09D-1D75265C200E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"703da0df8fda1ad0e54865475838043f0e379036","datavalue":{"value":"4037584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098765$6AAA3883-6022-4A8F-B7B8-3DD42F2BC914","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$C9B686E6-E42A-4BE2-916A-DEC0908DC4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$78490704-E3E6-491B-81CB-A0EF4941F688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$F5F3EBAA-726F-4B9A-9BFA-8871239C2441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$80E8ACF9-1C3C-4051-B6E8-D0DDE1DB1D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69d0c99f1e5283b31715a9c7d799852fe62c506e","datavalue":{"value":"shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$C080EFB1-D5FF-4044-B8B0-0A7D578AC886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b20b1a0fa47e88dc0fedbde51dd12f4a747910e","datavalue":{"value":"fixed start and end time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$AC2AE82C-1D1A-424C-A04A-D00F0FE6CDC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9c50e166b3bdd3d4624c14c188b82f1a7aeb2da","datavalue":{"value":"identical machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$89464765-B4E4-44AA-8753-5EEB14CA731A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098765$12B10B32-BA9F-471D-B57F-703CB67B9338","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":"Q1098765$3823CCB7-94F7-42CD-B54C-29C0F04B586A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$F2DDAEF1-6A80-4C8E-B77A-1BAAFFB2D774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$32E57FD7-D4F6-4606-8567-F826227E39CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14079f9b550ba1f661483da97df5df73cda997ac","datavalue":{"value":{"entity-type":"item","numeric-id":1144050,"id":"Q1144050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$3F40F78F-0430-454F-935C-F6F6BE2781D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$732B665C-A8A9-4303-9745-31393FB0611A","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":"Q1098765$3E65302E-2B17-4725-B441-5D6CD313F28D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3540803e6c2941a79b658c1ad46488049de9a54a","datavalue":{"value":{"entity-type":"item","numeric-id":5966939,"id":"Q5966939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$A3ADC705-C32A-46CE-B20D-0B3560DF47AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$E103F48B-FC18-4CA4-9E1E-DB16F6C9F3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$C42EE345-36FA-4B0A-9EC5-8ACB554F8655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$08204E6D-4FF9-40E9-AE42-074A07F5EBA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$831DB06F-3D13-4B6F-8282-84084085D257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7a6c6b8ed22abfff754835104aaed55a1d4a80","datavalue":{"value":{"entity-type":"item","numeric-id":1140988,"id":"Q1140988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$F23A53FA-8C27-43B3-BF07-078D42002B1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098765$DEDC601C-0E8A-4DE2-828A-809180411CAF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b8c7ed2089befc89ac2a3d18a3b8e2d5642ec88","datavalue":{"value":{"entity-type":"item","numeric-id":1331962,"id":"Q1331962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"602fa0664f07d453b3cc1686774041cd1421a6bf","datavalue":{"value":{"amount":"+0.8665919303894043","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":"Q1098765$71B2CA82-F752-43F7-A80C-0D2AA1F4648E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18f4e8f2a7c1db3b21ddc0345eec5701f6405636","datavalue":{"value":{"entity-type":"item","numeric-id":1319043,"id":"Q1319043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66a0c284332a225a4f11a1b3dfb52336259e0750","datavalue":{"value":{"amount":"+0.817467212677002","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":"Q1098765$AD9F6D19-F82B-43EF-BD81-AB985080832E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"775fe3572ddd97c4606b116aaca36777a40bb846","datavalue":{"value":{"entity-type":"item","numeric-id":2564884,"id":"Q2564884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43b5ea882a0956821c72d976a123b4f98375aadd","datavalue":{"value":{"amount":"+0.8165537118911743","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":"Q1098765$E6B9C8E0-B572-4637-8B07-460CDAE5A203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4741c2d07c5dcf50860aca4a410ad887f8d31162","datavalue":{"value":{"entity-type":"item","numeric-id":3972053,"id":"Q3972053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48768e78a6bf448f8d33e4466bba9afdd6ff8b85","datavalue":{"value":{"amount":"+0.8139153718948364","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":"Q1098765$E7C7C50A-90E1-47FA-9B22-6B26EA9DAB1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"965c35b88636d161c9a4e2945a5deac94e891b19","datavalue":{"value":{"entity-type":"item","numeric-id":3826354,"id":"Q3826354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c43c99ff485a9af358109b201ef95eb1bdd42d94","datavalue":{"value":{"amount":"+0.8104395866394043","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":"Q1098765$73D218AE-BC8F-45C2-ADF9-091FEA0D225B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1098765","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1098765"}}}}}