{"entities":{"Q1667046":{"pageid":1677787,"ns":120,"title":"Item:Q1667046","lastrevid":68094609,"modified":"2026-04-12T21:23:34Z","type":"item","id":"Q1667046","labels":{"en":{"language":"en","value":"Parallel-machine scheduling with time-dependent and machine availability constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6927682"}},"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":"Q1667046$7454428D-928D-4C2D-8B38-729C39190E9B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"491099f14ef5131d9201fadb5a73db1535044aad","datavalue":{"value":{"text":"Parallel-machine scheduling with time-dependent and machine availability constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1667046$9A8946F1-1BBF-4334-9D29-4DB3DE4DE685","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"915f02d7b6759ad20c7d9c6c2d3cfaf4b01cab4f","datavalue":{"value":"1394.90294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$652F8A32-9A09-48EE-9E0A-86E1889E4DB2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"417cd1a70cabd42b31f2d52870bf01bbc4c7d438","datavalue":{"value":"10.1155/2015/956158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$524FB046-70C7-46D8-8552-89B44ADCA798","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be2590c94235b28c1d0b2f670d0b6210b856d1b3","datavalue":{"value":{"entity-type":"item","numeric-id":384191,"id":"Q384191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$8D43896D-A605-484E-9D33-B4437548ACF0","rank":"normal"},{"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":"Q1667046$CB781AAE-CF9A-463C-98B6-765BEF63E5A0","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":"Q1667046$BC76AAEF-5EDB-4991-A047-8197D1BED3BE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"07d78b2809f727a96c8c6621733f1ab3a1973328","datavalue":{"value":{"time":"+2018-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1667046$46D9288F-7B86-42DE-A1BD-09899D98E797","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f90b1b459b7970a6ffc7046b4a2f0999cfded6a","datavalue":{"value":"Summary: We consider the parallel-machine scheduling problem in which the machines have availability constraints and the processing time of each job is simple linear increasing function of its starting times. For the makespan minimization problem, which is NP-hard in the strong sense, we discuss the Longest Deteriorating Rate algorithm and List Scheduling algorithm; we also provide a lower bound of any optimal schedule. For the total completion time minimization problem, we analyze the strong NP-hardness, and we present a dynamic programming algorithm and a fully polynomial time approximation scheme for the two-machine problem. Furthermore, we extended the dynamic programming algorithm to the total weighted completion time minimization problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1667046$A4E58C70-5929-413E-82DB-A4258A32C06C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$CB15D3FF-7858-42DB-8885-76CCA2DD306F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ff76952a47b8b1b8fdfadc2eb7466e911457ca9","datavalue":{"value":"6927682","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$AF469977-ED1D-4CE8-A668-7B8BD1BE9F04","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":"Q1667046$44DB9B6E-0560-42F8-BEF0-C5BAD24EB205","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d0a1980369c3260ce4a3d1bf27aeb55942dc369","datavalue":{"value":"https://doi.org/10.1155/2015/956158","type":"string"},"datatype":"url"},"type":"statement","id":"Q1667046$07FECDB5-7D50-4B10-BCD2-979F58C9A583","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"faed764f6e742cee2df3a8b98a4fa7f637a23f4f","datavalue":{"value":"W1891127169","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$EA57AFCB-76AF-4AE9-A0CB-EDBFC06A24A8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0ff99b14a70552bcbe10c4ccf6dd0859a4599061","datavalue":{"value":"Q59120038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1667046$C3CA222C-856E-4350-98F8-0829407525DA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"144b297cf2cd29decc141eec69fe1d4cd1e5a4cc","datavalue":{"value":{"entity-type":"item","numeric-id":938826,"id":"Q938826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$9D42FC70-ADEA-4F59-BA2A-29B1402D8100","rank":"normal"},{"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":"Q1667046$C69E1956-E52F-4BB5-ADB2-2BBD9311A1F5","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":"Q1667046$BB9791DA-41F4-4153-A8B2-E611922FEB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1000e19e12343aead8e376d617d3168ba049c3d3","datavalue":{"value":{"entity-type":"item","numeric-id":4934199,"id":"Q4934199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$D49EB3D8-80D2-4BCE-9AC6-D1C5E0E54777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ada29d2bd676ee832890ce6dfcbaa3a831bac6f","datavalue":{"value":{"entity-type":"item","numeric-id":2564885,"id":"Q2564885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$FCE36575-5FD0-4D3A-BCA6-BC9FE97CEBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc743c5fedd5716698252e18e6e72dd53c6f0c4","datavalue":{"value":{"entity-type":"item","numeric-id":1014400,"id":"Q1014400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$58770665-772C-4D87-B55E-006504A182F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2b2e8ea5857f0dd2acda570926e2eadb2ac4be3","datavalue":{"value":{"entity-type":"item","numeric-id":2508968,"id":"Q2508968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$F0580F4E-92D8-4D94-9B92-B199CF5DC467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"274a0abd721f0817d3eeee70ecf69b53f9150b6f","datavalue":{"value":{"entity-type":"item","numeric-id":2379562,"id":"Q2379562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$CE244EE1-5252-4651-8146-8B7D13056A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bc9eae67a228542120947bc1aaccdb16886e369","datavalue":{"value":{"entity-type":"item","numeric-id":620936,"id":"Q620936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$686E207D-2B36-454D-A835-3ADFCB578E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c24f21760531c5ae9488c65ea21da1f565689576","datavalue":{"value":{"entity-type":"item","numeric-id":2920364,"id":"Q2920364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$763C84F4-803C-454C-BB5F-C1B7BDC61153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5abeccca1315aac5d0a6d4683024d0c10d5b07e1","datavalue":{"value":{"entity-type":"item","numeric-id":837167,"id":"Q837167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$9F1FA9DA-5AA1-4783-8793-7D5D2ED2E4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46959b35b69afed96c220265e215b7370e3eab73","datavalue":{"value":{"entity-type":"item","numeric-id":391224,"id":"Q391224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$DBF12751-C031-4DE6-B89A-159AC803034F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4908d98c502afac1b40bbe1aa8b2003555524b9","datavalue":{"value":{"entity-type":"item","numeric-id":4427320,"id":"Q4427320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1667046$789E3884-7010-418B-9E1A-20E1B9937AF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63bd930c6b535009b1fdcc8a49a65664e359069e","datavalue":{"value":{"entity-type":"item","numeric-id":2257611,"id":"Q2257611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa32ba9db297e3b7e193cc3ae526ae01862dfa09","datavalue":{"value":{"amount":"+0.931102216243744","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":"Q1667046$8CA17DE0-D25B-40BB-91C1-F6FF7662C998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8583ea9a68a7066a28b42cfd098d9b1eefa7e367","datavalue":{"value":{"entity-type":"item","numeric-id":1923596,"id":"Q1923596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1b0465d3425ccb1897dc604ca3dbcd106bbe3ec","datavalue":{"value":{"amount":"+0.8724712133407593","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":"Q1667046$1F4D138A-08D4-4084-B621-367A09DCF3DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dcf4cf319c29fafc3fed15966c17919e36f5a8b","datavalue":{"value":{"entity-type":"item","numeric-id":3180917,"id":"Q3180917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82350dd80ad0ac687b0dac5ee52f6293ae8678e6","datavalue":{"value":{"amount":"+0.8719261884689331","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":"Q1667046$E5F9749D-972D-4C68-8BDD-580A07B84E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4a84aa0b2047fd88a8da88adcdea491d4657dc0","datavalue":{"value":{"entity-type":"item","numeric-id":2956870,"id":"Q2956870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9baafe44fe1e9e2beb476646c72993066e830e75","datavalue":{"value":{"amount":"+0.8714737892150879","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":"Q1667046$C64DAB5B-02B1-4B32-AA29-04E31EE777B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47f19b37a8151f82d236dcc292ba118f2dbdab0a","datavalue":{"value":{"entity-type":"item","numeric-id":2481965,"id":"Q2481965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e48a9111e2d6bd421bab6535568a9650f5191ce","datavalue":{"value":{"amount":"+0.8703347444534302","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":"Q1667046$B793588F-23F3-4F70-88A9-5B6FC2891C7F","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":"Q1667046$26898C86-8775-40C0-92B2-3FC7CB09ABF6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel-machine scheduling with time-dependent and machine availability constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel-machine_scheduling_with_time-dependent_and_machine_availability_constraints"}}}}}