{"entities":{"Q5946822":{"pageid":8123624,"ns":120,"title":"Item:Q5946822","lastrevid":47688298,"modified":"2026-01-02T10:45:45Z","type":"item","id":"Q5946822","labels":{"en":{"language":"en","value":"Local search algorithms for a single-machine scheduling problem with positive and negative time-lags"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1660379"}},"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":"Q5946822$231CF101-2F3E-423F-8B62-43D5F07F5028","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b06fa6b79cf53a56b3dd4b1fc629d48c68b3838d","datavalue":{"value":{"text":"Local search algorithms for a single-machine scheduling problem with positive and negative time-lags","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5946822$AB8AB5AB-9327-4D9A-BE0A-6033D0E67511","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a97d53f3edb6aa3d60e79d88c4f0c744d9d63b31","datavalue":{"value":"1010.90023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$6E4F3024-818D-4FC2-802A-70831BEBBDC3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fca1f643b3cbdfbb9248b374f0c7c7d1e10e0fd2","datavalue":{"value":"10.1016/S0166-218X(00)00315-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$38F659D5-47F7-43E5-A810-B242CC98670F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"73a9b9084633fc1972351d3b3abafe9d9381f2ab","datavalue":{"value":{"entity-type":"item","numeric-id":322694,"id":"Q322694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$AD72A7DA-ABA8-4EC0-B901-853A617A8858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a27607d22f87f23b15ab6a090d9ee195369cee22","datavalue":{"value":{"entity-type":"item","numeric-id":210523,"id":"Q210523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$16487391-B52A-46FF-A62F-7EB353788C0F","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":"Q5946822$F258B8CC-E051-478E-90A1-6AB7D52F25AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"231746dd1b162532443840a32e2f1ac3f5dc4bf7","datavalue":{"value":{"time":"+2002-07-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5946822$120201C5-E3F6-4060-9411-4A3958166283","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a3577ca3df4bfacea4e2f2b1a9a980c70611b787","datavalue":{"value":{"entity-type":"item","numeric-id":439606,"id":"Q439606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$1756479C-E170-459E-9A72-0B2A89C57CDA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$F16533B2-46B8-417A-9264-7FC69BDC4E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$B3BB3D29-7927-447F-97EA-4BE6ACEC64EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$AE1EA14D-8E2D-4176-BDD4-3FBBDF135DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$F1DF75EB-425A-4731-B1C0-698060FF05B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1cae19a56786eba8957e8781c7611122de0163e2","datavalue":{"value":"1660379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$73C361BC-2737-472A-80A9-B086F328B256","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdb89e20ab61117413f44de2a2591d4926c9392f","datavalue":{"value":"time-lags","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$9CBABA11-349B-443C-A91D-40A1799197A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8e00475554cb95f00d16db197d5817dede1318d","datavalue":{"value":"tabu search","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$B0EE9E5D-1952-47E7-A4D8-A6A8241EB728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$54164516-DE6A-45AE-AA25-6090023BD564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afd89d31745de14a6efd9fa3fccdb2096dc99674","datavalue":{"value":"single-machine scheduling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$C30A7BF6-C74A-41D9-ABFE-5E415BE97E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39a1850bcefc4d98848434c7caf2e01068c9332f","datavalue":{"value":"Zbk 0693.90047","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$C0B51B6E-3DFE-453D-9A4B-391597FB0355","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":"Q5946822$B55BFAA6-33FE-4331-A5CA-24B644D9775C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"66f1ca0cd4fdcef455e8e38147a4aab1efab670d","datavalue":{"value":{"entity-type":"item","numeric-id":4339078,"id":"Q4339078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$9B1910A7-FB1D-4FD2-96EE-0E5ADFAC5480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$5ED5375F-2B68-4B71-BAAC-CDD4CD1FEB96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2a1885126ef9e068f233b48ff9face027ee5bf","datavalue":{"value":{"entity-type":"item","numeric-id":3468865,"id":"Q3468865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$304872F6-89B7-4895-BDE4-57CD40D73BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654fd7309d900325e2212c65f5cea6f4b2e4d11f","datavalue":{"value":{"entity-type":"item","numeric-id":4838077,"id":"Q4838077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$850E14A4-4D8C-4ADE-8919-6E2F11E3C831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e52b578483f13df21fd15f653ca95f7877059f3e","datavalue":{"value":{"entity-type":"item","numeric-id":1293191,"id":"Q1293191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$1F70E603-D9D7-4DB4-A1C0-2FFA6EA6AF42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae876ac61efc171ef5bb969067a86396ebaa9a9e","datavalue":{"value":{"entity-type":"item","numeric-id":1363739,"id":"Q1363739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$2F32E69B-CF6C-4665-AA4B-7F3871589107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b54620eb6ca0276fd6bb7ac51226b48357c9dd1c","datavalue":{"value":{"entity-type":"item","numeric-id":1327223,"id":"Q1327223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$031051C0-2A6C-4F70-A689-C49C4CA87BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f1d093b01eb63a522b353371a5cda71ab1c0889","datavalue":{"value":{"entity-type":"item","numeric-id":1162927,"id":"Q1162927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$AB3AB484-5420-4F88-87D5-6C5E43BB39CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b544304cec3dda02e1256aa58efcb94e2a4084","datavalue":{"value":{"entity-type":"item","numeric-id":1303751,"id":"Q1303751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$8C647074-3B22-4B6A-9FC6-2BC2AEA6DD68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71eb2928472de986a7c52241317623fb1e6bcc02","datavalue":{"value":{"entity-type":"item","numeric-id":2367003,"id":"Q2367003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$DABF3A03-3608-4CA7-A285-7C9D1D1FA818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f81bb766858d58a18def4824c548d9a969bcc75","datavalue":{"value":{"entity-type":"item","numeric-id":4015267,"id":"Q4015267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$B8CCE474-61CD-43CC-AF0F-F23CAE776E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d61eb7d9a58a3113cab166621a33b6b0781faac","datavalue":{"value":{"entity-type":"item","numeric-id":1083026,"id":"Q1083026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$4FB1E9C3-C941-4F63-8F84-E2523059A482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86b63e0b91165686396c9310d9b550d2f83471f0","datavalue":{"value":{"entity-type":"item","numeric-id":1317529,"id":"Q1317529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$400565E9-5862-45B1-9DF0-E09C8DFF1496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307dd58a85ae038e43c182ba89cd767a5a3fec35","datavalue":{"value":{"entity-type":"item","numeric-id":4363639,"id":"Q4363639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$CED1448D-0D18-4247-AD51-D4807F79B4B7","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":"Q5946822$A05CA22C-292E-4D85-BBEA-260763796C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f38345f41d2fdd04972015c7c63bb38dd89a2db","datavalue":{"value":{"entity-type":"item","numeric-id":2366085,"id":"Q2366085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$66C0D266-AD42-4174-9EAF-767CC9EF4766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f99fdf46c6c12c3f0b58acc4f6131548de3d5d23","datavalue":{"value":{"entity-type":"item","numeric-id":1342279,"id":"Q1342279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$E05DBFC0-5CBE-44C5-BE01-D2CA5C5112B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1521ac972d69258156bb3f18e704a2c4eddefee","datavalue":{"value":{"entity-type":"item","numeric-id":1331566,"id":"Q1331566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946822$81057536-2559-4046-80A4-73E5EC053D58","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"94ed6cb25cd980bbd1871f30d78bb61c5341127a","datavalue":{"value":"Q126583270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946822$22F0A778-881F-4DFF-BFFF-9E96B04184AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"61b35a0737c460a478a023be498d7ffedc80bd47","datavalue":{"value":"The authors consider the following scheduling problem. Let \\(J=\\{1,2,...,n\\}\\) be a set of \\(n\\) jobs with processing times \\(p_1, p_2, ..., p_n\\) to be scheduled without preemption on a single machine. There is a set of relations called time-laggs of the form \\(S_i+d_{ij}\\leq S_j\\) for all \\((i,j)\\in R\\), where \\(R\\subseteq J\\times J\\) and \\(S_i\\) denotes the starting time of job \\(i\\), \\(i=1,2,...,n\\). If \\(d_{ij}\\geq 0\\), then job \\(j\\) cannot be started earlier than \\(d_{ij}\\) time units after the starting time of job \\(i\\) (minimal time-lag). If \\(d_{ij}<0\\), then job \\(j\\) cannot be started earlier than \\(|d_{ij}|\\) time units before the starting time of job \\(i\\) (maximal time-lag). NEWLINENEWLINENEWLINEA vector \\(S=(S_1, S_2,...,S_n)\\) of starting times of jobs determines a schedule. Such a schedule \\(S\\) is feasible if the intervals of processing of different jobs don't overlap and the time-lags are satisfied. The goal is to find a feasible schedule which minimizes the makespan \\(C_{\\max}=\\max_{1\\leq i\\leq n}\\{S_i+p_i\\}\\) if such a schedule exists. It should be mentioned that for this problem the question of whether or not a feasible solution exists, is already NP-complete [\\textit{M. Bartusch, H. M\u00f6hring} and \\textit{F. J. Rademacher}, Ann. Oper. Res. 16, 201-240 (1988; Zbl 0693.90047), \\textit{P. Bruckner, Th. Hilbig} and \\textit{J. Hurink}, Discrete Appl. Math. 94, 77-99 (1999; Zbl 0932.68006)]. NEWLINENEWLINENEWLINEIn this paper a local search approach for the problem under consideration is presented. A main obstacle for developing local search heuristics for this problem is the fact that the determination of an initial feasible solution is already a hard problem. In the paper this obstacle has been overcome by incorporating infeasible solutions in the search process. At first the authors give a network representation for the instances, formulate the problem of finding the best schedule for a given sequence of jobs (if such a schedule exists) as a longest path problem and develop an efficient method to determine such a schedule. Then local search methods are described. A basic method is a tabu search approach which starts with an ''infeasible'' sequence of jobs and which tries to guide the search to a feasible sequence. This basic routine is packed in an outer method where some diversification of the search is realized. Computational results based on instances resulting from shop problems are reported.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946822$339FCD7A-6469-4E94-AEE2-0913A82FC2CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c33005702f98ff261d910225974592d74c59ea0","datavalue":{"value":{"entity-type":"item","numeric-id":1293191,"id":"Q1293191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e9b50e353ac328ff957fdb60e55493eb60631c4","datavalue":{"value":{"amount":"+0.8554023504257202","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":"Q5946822$F707895C-32F3-4243-9238-15608D387EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a0d5d4a9e5758551e6d0a25a55aebab5b60f16a","datavalue":{"value":{"entity-type":"item","numeric-id":714025,"id":"Q714025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2169a5ff02dc6720b5604e57dbb493d3856fb0d7","datavalue":{"value":{"amount":"+0.8408442735671997","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":"Q5946822$C968AC84-BD98-466C-8378-DFA132F2802E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41a83204146aecd9f74266ac1ff4232726c8673e","datavalue":{"value":{"entity-type":"item","numeric-id":4345598,"id":"Q4345598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"480ed0f91c410143530349a5332f7fed85ccbf0f","datavalue":{"value":{"amount":"+0.8228018283843994","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":"Q5946822$EB328EBE-2231-48D0-9841-0E516CC18E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7deb625af9eba51b0cd1fc1e2e8746864d06ad8","datavalue":{"value":{"entity-type":"item","numeric-id":1969294,"id":"Q1969294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3a7afcc782a6cb9e2808645fe777339dfcc3ef8","datavalue":{"value":{"amount":"+0.8225159645080566","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":"Q5946822$3C8AB021-EE8D-476F-9108-C6216A1D994E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7217ebb8463f3322a8d0d81536c75aa3b29fa577","datavalue":{"value":{"entity-type":"item","numeric-id":2564876,"id":"Q2564876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2307a6c54ea671265ab4f625df6b3b6c0ac2c8a9","datavalue":{"value":{"amount":"+0.8065374493598938","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":"Q5946822$35E1B6C4-733A-4005-B1BB-2E95C3455514","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5946822","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5946822"}}}}}