{"entities":{"Q600836":{"pageid":602612,"ns":120,"title":"Item:Q600836","lastrevid":51117779,"modified":"2026-01-16T18:47:55Z","type":"item","id":"Q600836","labels":{"en":{"language":"en","value":"Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5809607"}},"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":"Q600836$BE2F154C-1BFB-444D-9F58-26E9E1D2232E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22581b2d41d072c3348f8004cb3d95868f12455d","datavalue":{"value":{"text":"Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q600836$3A526514-7752-4FD0-918A-88DADDB665FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5104f042cfe7a98fe7cacec213cde4edf74e82a3","datavalue":{"value":"1200.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q600836$FF23E0E6-BF65-4ED2-9A84-4A31688751AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a65b39db04d952bdbe11733d8815200c113f574","datavalue":{"value":{"entity-type":"item","numeric-id":248952,"id":"Q248952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$78820046-0002-4031-B211-045729C45985","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":"Q600836$35C3A1A3-E27E-4227-A846-EE74F731CB9F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39245fc27c04eb23fa7211454c51f34f7f46a9a0","datavalue":{"value":{"entity-type":"item","numeric-id":177699,"id":"Q177699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$4D4CBB72-0DBF-45E7-B9C9-D8553499E127","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"25cd2e09c2f6a58ceadbae256038e4067d8608c3","datavalue":{"value":{"time":"+2010-11-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q600836$717B3FE8-600B-46D8-AD2C-C5BF39C6DC29","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"375d60f68ac1e02d1688805665fcf11afd5dcd4c","datavalue":{"value":"In this paper multi-slot just-in-time scheduling problems are considered. Given is a set of jobs \\(j=1,\\ldots,n\\) where each job \\(j\\) has a processing time \\(p_j\\) and a due date \\(d_j\\). The objective is to schedule all jobs on a given number of parallel machines in time slots of length \\(L\\) such that job \\(j\\) is completed exactly at its due date in one time slot (i.e. at time \\(iL+d_j\\) for some integer \\(i \\geq 0\\)) and the makespan is minimized.  In this paper an \\(O(n \\log ^2 n)\\)-time algorithm is presented for the single machine case and an \\(O(n \\log n)\\)-time algorithm for an arbitrary number \\(m>1\\) of parallel machines where \\(p_j \\leq d_j\\) for all jobs \\(j\\) holds. Finally, for the general case on \\(m>1\\) parallel machines a polynomial-time approximation algorithm with constant worst-case performance ratio is proposed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q600836$629FFF54-23EF-4145-A929-EBE699779A6A","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":"Q600836$2C0FCED4-92D0-43FA-B5F6-DE7DE0F37E85","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q600836$7E11B8E3-840A-4036-8E70-69FCA34517D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e427cd450d17fbce13a6d78da50bee08b956b507","datavalue":{"value":"5809607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q600836$4E2219F5-6577-4C0A-9C29-A3190DB6EBCC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c58058d708bdb1b26c114ed02d3c4ad44ca956f","datavalue":{"value":"just-in-time scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q600836$13BF67A0-8883-44B8-BBB6-A26B18CC66D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72bf1bd12f072b8ea4bb41164d8dbc33d014dfd3","datavalue":{"value":"makespan minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q600836$F5128B15-6B99-4CCE-97F9-F93F80C99099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a6ecc4d4c15ad34ded95961f1207e29e7fe698f","datavalue":{"value":"multi-slot","type":"string"},"datatype":"string"},"type":"statement","id":"Q600836$1B523E43-EF9D-40D8-BA71-D1A02BF88EF6","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":"Q600836$34ACD5F3-2443-426F-9BDC-74CB5B9B3C96","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d657df32ea52cc2d6503d6c64121241542f9d4c9","datavalue":{"value":"https://doi.org/10.1007/s10951-009-0139-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q600836$98E717FE-3E19-41EC-BC42-95BAC2EC0B99","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"66ab0c1a07bd203e6f3c93d54535f40b7514cd0d","datavalue":{"value":"W2136004943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q600836$90CB5948-F59C-4933-8DC6-955DA3B6769C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec402beae0b5af1ec240175610cacba870a58d7","datavalue":{"value":{"entity-type":"item","numeric-id":1198648,"id":"Q1198648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$33A1796E-F73B-4A0F-BC53-BA8482ACC67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76b59f2fe0b035d9f6b252635266d8c9bfd51e66","datavalue":{"value":{"entity-type":"item","numeric-id":4380372,"id":"Q4380372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$90869F62-A5A1-4FBC-8B20-88E0CBB742B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224e41cb9b44158662f0345cccfc300829f9b2e6","datavalue":{"value":{"entity-type":"item","numeric-id":1893157,"id":"Q1893157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$2B371532-B28A-4745-AB6B-E2B4081810A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10d9726bd833217e3e0ca3cedd2d986dbf6d0d6","datavalue":{"value":{"entity-type":"item","numeric-id":5331678,"id":"Q5331678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$18B7522C-936B-4DBE-8A23-3C518225F890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$24FF575E-D03F-4018-8298-1854B837F31C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6142e7a2805968d49d79b211fecb35a52e36ca6d","datavalue":{"value":{"entity-type":"item","numeric-id":5959375,"id":"Q5959375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$0A1DB85F-958C-44BC-8857-DCFEAB589E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3558e6e285244ddbda3fdda630991188e6765ae6","datavalue":{"value":{"entity-type":"item","numeric-id":2644259,"id":"Q2644259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$51F8322D-E04C-4DE0-B422-E01EA6D06F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f22398e47e21a693448faebe371c551f0c7c66f0","datavalue":{"value":{"entity-type":"item","numeric-id":947706,"id":"Q947706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$D9E03279-8985-4335-8290-2EAC757EA758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f642e375facb91603804fa224278b8ab3bef19fe","datavalue":{"value":{"entity-type":"item","numeric-id":3446812,"id":"Q3446812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$BDF45FF1-D381-4F2C-A6F1-221AB9D84011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2d7941d0b26099a80a70765368bbd5212826ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3677509,"id":"Q3677509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$5B6362D4-F1FF-4010-9347-3285AFF905BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b441fd113f76b8d9dedf9e38d2d20ca895fa66ae","datavalue":{"value":{"entity-type":"item","numeric-id":4050411,"id":"Q4050411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$D0523A03-B22E-4B58-90A4-59BADA8FFFFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e849acd017a7fa3560987fa48019e2db116bcf02","datavalue":{"value":{"entity-type":"item","numeric-id":2464402,"id":"Q2464402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q600836$A35AAF10-9D06-4DE7-9D58-3DACFEE919B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67c6b13a635d606cd28b7e3987a2ab9ee9efcbc0","datavalue":{"value":"10.1007/S10951-009-0139-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q600836$6C91335E-5C09-4C90-8C00-3F45F306AE3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ae154a2c72edd443dc22d881a273512045d8084","datavalue":{"value":{"entity-type":"item","numeric-id":4652816,"id":"Q4652816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c11350da0c5a66505b5d908ad2d6e62bb01436f","datavalue":{"value":{"amount":"+0.8261063694953918","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":"Q600836$65952A66-A6E2-4ECE-A90B-76422CA3561D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c99eb03fed9fe054d5df73b89a517ccee3f8251","datavalue":{"value":{"entity-type":"item","numeric-id":2387307,"id":"Q2387307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"307ab5abbe72028cf002dd3666f70b0f4fe03ae1","datavalue":{"value":{"amount":"+0.8164359927177429","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":"Q600836$E0AFA876-3959-4E43-89F2-582976A182A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9744a5b655b462bd94b6664e3d21cf4966f4b01b","datavalue":{"value":{"entity-type":"item","numeric-id":975765,"id":"Q975765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b3a3dca1b114f9fa6d10d570fab9b7144250fa6","datavalue":{"value":{"amount":"+0.8125764727592468","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":"Q600836$B29C2175-F207-4E2E-B7B8-5B6BD5A9FFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3db1e50b9c19de05331150f3e820d2cefd8201ab","datavalue":{"value":{"entity-type":"item","numeric-id":421784,"id":"Q421784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9573bf456c3247efecb2e805c221ea87268d0bb5","datavalue":{"value":{"amount":"+0.8110995292663574","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":"Q600836$2785F2B6-A062-4C4C-9675-F362D5BAB7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4beac24c64c055955fd2fcca1f7fc3c56d41cae7","datavalue":{"value":{"entity-type":"item","numeric-id":5959375,"id":"Q5959375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aaa343a960a3bce00e32b0344cc3c30455611b4","datavalue":{"value":{"amount":"+0.8011148571968079","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":"Q600836$22067677-6A20-4787-964D-51191B1AD916","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:600836","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:600836"}}}}}