×

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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems

Software:

PESPLib
PDFBibTeX XMLCite
Full Text: DOI

References:

[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, (Proc. of the SIGPLAN’88 Conf. on Prog. Language Design and Implementation. Proc. of the SIGPLAN’88 Conf. on Prog. Language Design and Implementation, Atlanta, USA (1988)), 308-317
[3] Carlier, J.; Chretienne, P., Les Problèmes d’Ordonnancement (1988), Masson: Masson Paris · Zbl 0494.90040
[4] Carlier, J.; Chretienne, P., Timed Petri nets schedules, (Rozenberg, G., Advances in Petri Nets (1988), Springer Verlag: Springer Verlag Berlin), 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, (Proc. of the ACM Int. Conf. on Super-computing. Proc. of the ACM Int. Conf. on Super-computing, Saint Malo, France (1988)), 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: W.H. Freeman and Company New York · Zbl 0411.68039
[9] Hanen, C., Microprogramming using timed Petri nets, (Rozenberg, G., Advances in Petri Nets (1989), Springer Verlag: Springer Verlag Berlin), 236-261
[10] Kogge, P. M., The Architecture of Pipelined Computers (1981), McGraw Hill: McGraw Hill New-York · Zbl 0476.68004
[11] Lam, M., A systolic array optimizing compiler, (PhD dissertation (1987), Carnegie Mellon University)
[12] Matsuo, H., Cyclic sequencing problems in the two machine permutation flowshop: complexity, worst case and average case analysis, (Technical Report (1988), Graduate School of Business, University of Texas: Graduate School of Business, University of Texas Austin) · 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: Prentice Hall Englewood Cliffs, NJ
[15] Pinson, E., Le problème de job-shop, (Thèse de l’université Paris 6, Cahiers de l’IMA 89/2 (1988), Université Catholique de l’Ouest: Université Catholique de l’Ouest Angers) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.