zbMATH — the first resource for mathematics

Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. (English) Zbl 0801.90061
Summary: This paper tackles a cyclic scheduling problem with disjunctive resources called the recurrent job-shop. It is aimed to show structural properties of feasible schedules on which efficient algorithms could be based. The problem is proven to be NP-hard and is formulated as a mixed linear program. We prove that any feasible solution is associated with a valuation called a conservative height on the graph of constraints. Computing the critical circuit provides the best solution associated with a given conservative height. Bounds on the feasible heights and on the throughput based on these properties are then stated. Finally we propose a branch-and-bound enumeration procedure and two heuristics solving the problem. We report numerical experiments.

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI
[1] Adams, A.; Balas, E.; Zawack, Z., The shifting bottleneck procedure for the job-shop scheduling, Management science, 34, 391-401, (1986) · Zbl 0637.90051
[2] Aiken, A.; Nicolau, A., Optimal loop parallelization, (), 308-317
[3] Carlier, J.; Chretienne, P., LES problèmes d’ordonnancement, (1988), Masson Paris · Zbl 0494.90040
[4] Carlier, J.; Chretienne, P., Timed Petri nets schedules, (), 62-84 · Zbl 0667.68051
[5] Carlier, J.; Pinson, E., A branch and bound method for solving the job-shop problem, Management science, 35, 2, 164-176, (1988) · Zbl 0677.90036
[6] Cohen, G.; Dubois, D.; Quadrat, J.P.; Viot, M., A linear system theoretic view of discrete event process and its use for performance evaluation in manufacturing, IEEE transactions on automatic control, 30, 2, 210-220, (1985) · Zbl 0557.93005
[7] Eisenbeis, C., Optimization of horizontal microcode generation for loop structures, (), 453-465
[8] Garey, M.R.; Johnson, D.So., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York · Zbl 0411.68039
[9] Hanen, C., Microprogramming using timed Petri nets, (), 236-261
[10] Kogge, P.M., The architecture of pipelined computers, (1981), McGraw Hill New-York · Zbl 0476.68004
[11] Lam, M., A systolic array optimizing compiler, ()
[12] Matsuo, H., Cyclic sequencing problems in the two machine permutation flowshop: complexity, worst case and average case analysis, () · Zbl 0731.90041
[13] Munier, A., Résolution d’un problème d’ordonnancement cyclique a itérations indépendantes et contraintes de ressource, (1991), To appear in RAIRO
[14] Muth, J.F.; Thompson, G.L., Industrial scheduling, (1963), Prentice Hall Englewood Cliffs, NJ
[15] Pinson, E., Le problème de job-shop, () · Zbl 0677.90036
[16] Roundy, R., Cyclic schedulès for job-shops with identical jobs, (1988), School of Operation Research and Industrial engineering, Cornell University, T.R. 766 · Zbl 0770.90036
[17] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM journal of discrete mathematics, 2, 4, 550-581, (1989) · Zbl 0676.90030
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.