×

zbMATH — the first resource for mathematics

Benchmarks for basic scheduling problems. (English) Zbl 0769.90052
Summary: We propose 260 randomly generated scheduling problems whose size is greater than that of the rare examples published. Such sizes correspond to real dimensions of industrial problems. The types of problems that we propose are: the permutation flow shop, the job shop and the open shop scheduling problems. We restrict outselves to basic problems: the processing times are fixed, there are neither set-up times nor due dates nor release dates, etc. Then, the objective is the minimization of the makespan.

MSC:
90B35 Deterministic scheduling theory in operations research
Software:
JOBSHOP; OR-Library
PDF BibTeX Cite
Full Text: DOI
References:
[1] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA journal on computing, 3, 149-156, (1991) · Zbl 0755.90039
[2] Beasley, J.E., OR-library: distributing test problems by electronic mail, Journal of the operational research society, 41, 1069-1072, (1990)
[3] Bräsel, H.; Tautenhahn, T.; Werner, F., Constructive heuristic algorithms for the open shop problem, () · Zbl 0796.90031
[4] Bratley, P.; Fox, B.L.; Schrage, L.E., A guide to simulation, (1983), Springer-Verlag New York · Zbl 0515.68070
[5] Carlier, J., Problèmes d’ordonnancement à contraintes de ressources: algorithmes et complexité, ()
[6] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management science, 35/2, 164-176, (1989) · Zbl 0677.90036
[7] Glover, F., Tabu search - part I, ORSA journal on computing, 1, 190-206, (1989) · Zbl 0753.90054
[8] Kleinau, U., On some new methods for solving machine scheduling problems, ()
[9] Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Sequencing and scheduling, () · Zbl 0482.68035
[10] Lawrence, S., Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement), (1982), Graduate School of Industrial Administration, Carnegie Mellon University
[11] Muth, J.F.; Thompson, G.L., Industrial scheduling, (), 225-251
[12] Taillard, E., Parallel taboo search technique for the job shop scheduling problem, () · Zbl 0807.90066
[13] Taillard, E., Some efficient heuristic methods for the flowshop sequencing problem, European journal of operational research, 47, 65-74, (1990) · Zbl 0702.90043
[14] Widmer, M.; Hertz, A., A new heuristic for the flowshop sequencing problem, European journal of operational research, 41, 186-193, (1989) · Zbl 0671.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.