In the past three decades, local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization that is attracting ever-increasing attention. Local search ...is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in reasonable time. Local Search in Combinatorial Optimization covers local search and its variants from both a theoretical and practical point of view, each topic discussed by a leading authority. This book is an important reference and invaluable source of inspiration for students and researchers in discrete mathematics, computer science, operations research, industrial engineering, and management science. In addition to the editors, the contributors are Mihalis Yannakakis, Craig A. Tovey, Jan H. M. Korst, Peter J. M. van Laarhoven, Alain Hertz, Eric Taillard, Dominique de Werra, Heinz Mühlenbein, Carsten Peterson, Bo Söderberg, David S. Johnson, Lyle A. McGeoch, Michel Gendreau, Gilbert Laporte, Jean-Yves Potvin, Gerard A. P. Kindervater, Martin W. P. Savelsbergh, Edward J. Anderson, Celia A. Glass, Chris N. Potts, C. L. Liu, Peichen Pan, Iiro Honkala, and Patric R. J. Östergård.
We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or ...unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.
In memoriam Gerhard Woeginger Lenstra, Jan Karel; Rendl, Franz; Spieksma, Frits ...
Journal of scheduling,
10/2022, Letnik:
25, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Gerhard Woeginger has passed away. His colleagues Jan Karel Lenstra, Franz Rendl, Frits Spieksma and Marc Uetz commemorate a great scientist and dear friend.
Interval scheduling: A survey Kolen, Antoon W.J.; Lenstra, Jan Karel; Papadimitriou, Christos H. ...
Naval research logistics,
August 2007, Letnik:
54, Številka:
5
Journal Article
Job Shop Scheduling by Simulated Annealing van Laarhoven, Peter J. M; Aarts, Emile H. L; Lenstra, Jan Karel
Operations research,
01/1992, Letnik:
40, Številka:
1
Journal Article
Recenzirano
Odprti dostop
We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative ...improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times.
In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of ...complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.
PDF
