{"entities":{"Q2641218":{"pageid":2651961,"ns":120,"title":"Item:Q2641218","lastrevid":49467805,"modified":"2026-01-07T05:16:53Z","type":"item","id":"Q2641218","labels":{"en":{"language":"en","value":"A preemptive open shop scheduling problem with one resource"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4189463"}},"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":"Q2641218$EF9A29BA-BC26-4A55-B3A5-3715017D0F0D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28e1a722dfce5f294767b33d285acb7cb2283b24","datavalue":{"value":{"text":"A preemptive open shop scheduling problem with one resource","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2641218$A22A8ADA-083E-4B6F-8C6A-37B2AF0384AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa59a22457d5fdd153096f2da6b5d2b2db5d7833","datavalue":{"value":"0721.90046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$949CF6C7-83C2-45EF-928A-7989CE08C84E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9e7a9f1df3d230e49f93cccecad0d858fc175e0","datavalue":{"value":"10.1016/0167-6377(91)90080-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$72DA9219-D8B6-4EB5-8360-8E39E025E673","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"467bce3dcf8136ea7a4832a7c85d350a56e9a245","datavalue":{"value":{"entity-type":"item","numeric-id":224825,"id":"Q224825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$4A39B03D-52C8-4F90-8359-7529C9E99598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ea65ac05d3711d20bfd41cd5b0225d93e7a7d58","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$AEFC6692-14D3-4FF9-9586-13CB6E4FBF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"216e7a36a8992ef42057a8f0d0dcb9de6af5f9e9","datavalue":{"value":{"entity-type":"item","numeric-id":1575602,"id":"Q1575602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$F2C111B2-BC05-43B9-9837-2350D3C5C390","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$75E82050-AC8E-4C2C-A6AA-E208B9188735","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2641218$264E061C-1B94-4C6F-A636-79648269408D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"974850b3f68a788853cfb9a627b3034252bae95f","datavalue":{"value":"A preemptive open shop scheduling problem with nonrenewable resource leads to a problem of the following form. We are given a bipartite multigraph with the property that for all \\(i=1,...,n\\) and \\(j=1,...,m\\) there are \\(p_{ij}\\) parallel edges betweeen i and j. Furthermore there are positive integers \\(h_ 1,...,h_ q\\) with \\(\\sum^{q}_{i=1}h_ i=\\sum^{n}_{i=1}\\sum^{m}_{j=1}p_{ij}\\). Find an edge coloring with color sets \\(H_ 1,...,H_ q\\) such that  \\[  \\sum^{i}_{s=1}| H_ s| \\leq \\sum^{i}_{s=1}h_ s\\text{ for } i=1,...,q.  \\]  It is shown that this problem is NP-complete. For the special case that all \\(t_{ij}=1\\) necessary and sufficient conditions on the sequence \\(h_ 1,...,h_ q\\) for the existence of a solution of the problem are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641218$7655113F-99A3-4BD6-8989-87321D0DCB14","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"647403b42bff8e5868a53244a891290fdc1b119f","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$3812223C-BC60-4E54-9E23-22D01C1AE542","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$89E6B0E0-E9CF-4B07-A932-54769549C8D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$B26623E1-4E0C-4B9C-A42D-38B8FCF7B3B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$1925BAFF-F8E9-44A1-BE6F-57F9541387AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b870564c6ca13cc1eed9a800409c1aacda0c4bdf","datavalue":{"value":"4189463","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$F2C9BA4F-AF94-414C-979A-91100667B5BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35c5addf7e3b57d4d5f80d240f96e2e76b5f5a0d","datavalue":{"value":"preemptive open shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641218$FCB5D39A-1E01-464E-AA21-1CCA2FA6FBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec210975e05ad682265c1e7d09cd409b9880c2d","datavalue":{"value":"nonrenewable resource","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641218$7DDA2A3D-83E3-4E86-BC2E-D14D08E0C547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0f5676cd13972c82447aeb9b5b501dd066e7ae8","datavalue":{"value":"bipartite multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641218$101647C8-8EBF-4B66-B371-EC9F0C17CF87","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":"Q2641218$DDE58A44-B915-4D31-9DBE-BD2C14D76799","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"331e1a57d4eeb7bc85c511ee787079b276104816","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90080-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2641218$ED21AF49-2676-4CFA-B6B0-034348ED0C97","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dd7e36622d0c2bd7ff44a41a6aee909803473a7d","datavalue":{"value":"W2031705523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$07A50293-EE96-4B8E-9559-4836F4DB178E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bd341b7ef26462e5f26be8e5aa8415a3f777fbd4","datavalue":{"value":"Q57387909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$8F5085AF-BD14-4968-9ECE-F0F9E2A116A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$E33A405A-9164-422E-8E88-6C6A8F0EB785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a0c1fcd30d02a093c96c2df7bc144187934ce88","datavalue":{"value":{"entity-type":"item","numeric-id":3821925,"id":"Q3821925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$77CC9360-2879-4623-ADC4-DA83F0F53253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa982d8fefc867691dc6997af61a0ed87ed4ae33","datavalue":{"value":{"entity-type":"item","numeric-id":3830806,"id":"Q3830806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$E2CE4B00-7BB7-4E69-9604-1B4E62C37B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f4c9039cb0d9d8f16a51b6dc98241192bea20f9","datavalue":{"value":{"entity-type":"item","numeric-id":5604409,"id":"Q5604409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$6F765F90-0EF9-42FD-B3EE-99CEAFB6F588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fa5067d68506865f17652c185e6acdcfd2326b9","datavalue":{"value":{"entity-type":"item","numeric-id":1837625,"id":"Q1837625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$E67B979E-A25C-4D91-944E-FED3EE0CA853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfbd785c98ffff9164411c97d0cfacab892ef9ed","datavalue":{"value":{"entity-type":"item","numeric-id":4111095,"id":"Q4111095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$084859B9-8CF5-46B4-A48F-8DC433D5A648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2498a56aef19d26f3401cb300498210cdda99d07","datavalue":{"value":{"entity-type":"item","numeric-id":2546513,"id":"Q2546513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$3D4161CD-6FA2-4737-8164-9D5B319E0BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1d100291218ee3055d0233659bfb3e960399a04","datavalue":{"value":{"entity-type":"item","numeric-id":3315254,"id":"Q3315254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641218$2E482C95-1D7C-4717-94CD-3EB05CE52C72","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"11ab04af0882426c3b3eb0639dc22b39af20f2a6","datavalue":{"value":"journals/orl/WerraBK91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641218$8296A0FC-0732-4080-9797-7B88726766D1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebfffa8021edd052f6f8974099dbf5474cc657ea","datavalue":{"value":{"entity-type":"item","numeric-id":1186309,"id":"Q1186309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87211a8b8c5f88b0b615971c51ceb997fd596047","datavalue":{"value":{"amount":"+0.888522207736969","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":"Q2641218$83BEF1B3-9765-4CA8-9A4E-C28F7BD91420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cb6bd2be58ed67138284c0b7cf9c15935c4cec5","datavalue":{"value":{"entity-type":"item","numeric-id":1917354,"id":"Q1917354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8384fb275149d051dee987980208de70ad424bdf","datavalue":{"value":{"amount":"+0.8647503852844238","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":"Q2641218$4A1BEF3E-15EA-4089-B964-24B22D0410D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18281e0cdde1406348af659f420759ddbf996c0a","datavalue":{"value":{"entity-type":"item","numeric-id":835582,"id":"Q835582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5e89419829c652f7abfce0cc623a6ceb8276181","datavalue":{"value":{"amount":"+0.8431497812271118","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":"Q2641218$CCC3E6A7-4E24-4D40-9EBF-1616D136AD04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15cd741d2b99ac860be7a536f34edfc66ca23bef","datavalue":{"value":{"entity-type":"item","numeric-id":1911243,"id":"Q1911243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"269b17cde106ac19428498795e766c2f1f957a35","datavalue":{"value":{"amount":"+0.8208125829696655","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":"Q2641218$638A5FE1-CB4F-4C48-AD98-8F231BACF935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59e3af9aeed41237538dad61dc9f82a99c1de43e","datavalue":{"value":{"entity-type":"item","numeric-id":1058969,"id":"Q1058969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"862fec67f041c5c5d56459d1fb7757b938c9f953","datavalue":{"value":{"amount":"+0.8158802390098572","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":"Q2641218$9A3AA281-0B18-47E8-8EBA-DFD90F85B094","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2641218","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2641218"}}}}}