{"entities":{"Q554491":{"pageid":556258,"ns":120,"title":"Item:Q554491","lastrevid":51309974,"modified":"2026-01-17T17:12:06Z","type":"item","id":"Q554491","labels":{"en":{"language":"en","value":"Single machine scheduling problems with financial resource constraints: some complexity results and properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5935943"}},"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":"Q554491$C96F0DED-9E26-46A9-8774-547BFB5E6C64","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30beca3a9fc4ec478983cc9fecb50625dc586856","datavalue":{"value":{"text":"Single machine scheduling problems with financial resource constraints: some complexity results and properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q554491$74FF7D76-1967-4F04-943B-D189AEC37E64","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1283db0a80a20aacc744c92aecc456ea35d504fc","datavalue":{"value":"1229.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$FE88D0A9-1005-403C-A710-05FCF78D19F4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2deb57a21cb059006d12126715dc580842ce5c7b","datavalue":{"value":{"entity-type":"item","numeric-id":367637,"id":"Q367637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$18009977-FA3A-4946-A247-49C806D3728B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ca4811b5a017f1f37af6a345468f98b2693ddb5","datavalue":{"value":{"entity-type":"item","numeric-id":483268,"id":"Q483268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$D003B404-3A1C-437C-8DC4-AEDD45B29D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78641eb2f75653702db92c9a7fb811442353ea2b","datavalue":{"value":{"entity-type":"item","numeric-id":229433,"id":"Q229433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$CE054F85-70E9-48CB-84FA-BDE21E6CF68D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1f166790ec34f4b6b0fbf53f80bd31461e449db4","datavalue":{"value":{"entity-type":"item","numeric-id":177530,"id":"Q177530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$352E3175-36AD-45C5-86E9-9F0485D1E14E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c4f550430958fbc82f7f345b4735dd7bcd0b800f","datavalue":{"value":{"time":"+2011-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q554491$7F16822B-227A-4028-816B-D1DD33D79DC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02e8ef51656cc8ff189c937b627e053164dc6b94","datavalue":{"value":"In this paper single-machine scheduling problems with a non-renewable resource are studied. Given is a set of jobs \\(j=1,\\ldots,n\\) with processing times \\(p_j\\) which have to be processed on a single machine. Furthermore, a non-renewable resource is given, which becomes available at specified points in time and is consumed by the jobs. The goal is to find a feasible schedule respecting the resource constraints and minimizing a given objective function.  It is shown that the problem is strongly NP-hard for the makespan objective, minimizing the total tardiness (even if all due dates are the same) and that it is NP-hard for the total completion time. Afterwards, structural properties for special cases of the tardiness problem are studied. Finally, the so-called budget problem minimizing the makespan is considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q554491$C7411020-F2E6-4072-84B2-E74DD88F7D1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e47c7ebb56a1f0496381a9a28be5aa2e34301ed2","datavalue":{"value":{"entity-type":"item","numeric-id":210525,"id":"Q210525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$E653DEE6-FE24-4B7E-9195-6FDCC16827FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$23D04192-727D-428D-8B2E-8AE87CAE4662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3783afd39b9a4c0ecdd0e6ac842f765284c23884","datavalue":{"value":"91B32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$BAAEDA16-2FD6-497D-A9CF-833B93D13D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$CE894395-1B62-4B2D-852E-91F1D4CC82F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3cec692a3f6deea084100215aa7797c5da85e399","datavalue":{"value":"5935943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$2E0CE36D-E62A-46C2-BAED-7E4CAAF5CA44","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q554491$5E351E83-E2C8-45A1-A4DD-C75552AD3505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65b4f9eb271b550c15a509a792292836e560f4ef","datavalue":{"value":"non-renewable resource","type":"string"},"datatype":"string"},"type":"statement","id":"Q554491$E913D062-A543-41A6-BF3E-866294A98F8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q554491$569D33CC-14EF-4A9E-9ED2-BF889DEF02A3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8cd289dd9af5a6d54c653319d613a4de56e88087","datavalue":{"value":"Q57633864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$D640B363-2D79-4501-AB1C-CDE1573BF961","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":"Q554491$118FE066-5D05-4B9B-9147-B4CF2718B330","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f418683a6e826cda45f0d2e49451383095de341d","datavalue":{"value":"https://doi.org/10.1016/j.mathsocsci.2011.04.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q554491$452FFBA6-E87A-41A6-9575-E01C54CAC94B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b8891e22709e9ff6bc774ac85411c46d2ef6d06","datavalue":{"value":"W2108940302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$3CAF73BB-565B-4FE6-8D6F-D84E8DDED76A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ca3d18c88a987e2a43ee917e52a620e4f9d65dd","datavalue":{"value":{"entity-type":"item","numeric-id":1169397,"id":"Q1169397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$F0B92534-0526-4CFB-BFE5-CC245CE3C05C","rank":"normal"},{"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":"Q554491$EA85F776-9E28-483C-9AE9-8AB8C3FA138C","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":"Q554491$2733680F-95FB-49F7-B9C2-B06B69B36D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed33a4ae47e95fd5e48470dc21c33ac3001b3d4b","datavalue":{"value":{"entity-type":"item","numeric-id":3741388,"id":"Q3741388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$D434D376-BACD-4CAE-986C-A85A34DE2F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90324e6e93bcf2fdec5e5778fdf491c93fa57a58","datavalue":{"value":{"entity-type":"item","numeric-id":4124332,"id":"Q4124332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$B71A8CEC-F721-4E0F-9279-754815CC7BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c881df91ee6fc7272f8d7c580d2544390dc790","datavalue":{"value":{"entity-type":"item","numeric-id":1946412,"id":"Q1946412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$4E57B1D7-5DE1-4DC9-A295-A6EC576AABC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d8a3e2ff0ef67913f14b61224ec1e83161cff86","datavalue":{"value":{"entity-type":"item","numeric-id":732689,"id":"Q732689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$4B5CAEAA-C613-4F8E-BCCF-48C8CA27680E","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":"Q554491$1785E658-5717-4423-AF1B-B2691B36A7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d807bb530ca3619bb47aaf5ce63171cf411fca94","datavalue":{"value":{"entity-type":"item","numeric-id":1838424,"id":"Q1838424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$74EC5C8E-A167-4A07-B21F-89BE679DFDD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fbf1f93d677a110a45e460fdc01b5a729b35093","datavalue":{"value":{"entity-type":"item","numeric-id":791440,"id":"Q791440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$B088F15D-4C8C-4549-97D5-13AAA5927BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4110d61331386417e34b99ea41bcbfec22c8a5da","datavalue":{"value":{"entity-type":"item","numeric-id":1592283,"id":"Q1592283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$E0EF3A18-B2FD-4DD3-A96F-A2459D8C8CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"973d999ccf494757939367a7fecaab7a88836683","datavalue":{"value":{"entity-type":"item","numeric-id":3983497,"id":"Q3983497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q554491$B3C5A128-49E1-401C-B2DA-218FB41DC07B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"018b93753aa0e44883580e90b3c61dc33ee4dc9c","datavalue":{"value":"10.1016/J.MATHSOCSCI.2011.04.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q554491$3D5808B8-56A1-4FCA-BBEF-A20D1D65CB22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cc6524a685bce65c5b912294e554178b4485c35","datavalue":{"value":{"entity-type":"item","numeric-id":3804436,"id":"Q3804436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85e6bafe03efff327297f25f8c28c9474d53db42","datavalue":{"value":{"amount":"+0.8505626320838928","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":"Q554491$B0C3BD4C-6395-422F-B6F1-2E1CBFF7DF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb248db9bb5b5ee10e4d0a6c592edb676eeadfa3","datavalue":{"value":{"entity-type":"item","numeric-id":1371954,"id":"Q1371954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbcfeda1c9edb548f676414c8841c58169f1e5dd","datavalue":{"value":{"amount":"+0.8490230441093445","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":"Q554491$EDFF1D55-9907-4C9D-B0E9-BCD08EA19DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12926b821f68a53fffb5633411da957b96644912","datavalue":{"value":{"entity-type":"item","numeric-id":2078845,"id":"Q2078845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1998445bbe392f541e7cf5557424ff943c884e65","datavalue":{"value":{"amount":"+0.8366862535476685","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":"Q554491$5557B45A-F73A-4C80-A80B-B27AAFD12E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e0fa1de818fc19ca775d97abc8f1fc0e05da9bd","datavalue":{"value":{"entity-type":"item","numeric-id":3741388,"id":"Q3741388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"930355c6e2f5dc05703ec04925ecfad83d21ab22","datavalue":{"value":{"amount":"+0.8288441896438599","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":"Q554491$1163074D-B9E9-42FD-B9CD-61DF1331B36C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91b5c82bbc36a9724ef71c22c7a9e02830f09848","datavalue":{"value":{"entity-type":"item","numeric-id":2294889,"id":"Q2294889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"075ba5e89327c34090485d55106454320e9d946a","datavalue":{"value":{"amount":"+0.8277040123939514","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":"Q554491$863A6E5C-800D-4C1E-B00E-3065AB4440E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:554491","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:554491"}}}}}