×
Della Croce, F.; Menga, G.; Tadei, R.; Cavalotto, M.; Petri, L.

Cellular control of manufacturing systems. (English) Zbl 0784.90034

Eur. J. Oper. Res. 69, No. 3, 498-509 (1993).
Summary: The scope of this paper is twofold. Firstly, we propose augmented Lagrangian-based decomposition techniques for solving scheduling problems in manufacturing systems and then we show that the resulting decomposition of the mathematical problem lends itself to control systems with a topological cellular structure, and that it can be espoused very naturally with an object-oriented programming approach.

Cited in 2 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90B30 Production models

Keywords:

augmented Lagrangian-based decomposition techniques; object-oriented programming

Software:

JOBSHOP
PDF BibTeX XML Cite
\textit{F. Della Croce} et al., Eur. J. Oper. Res. 69, No. 3, 498--509 (1993; Zbl 0784.90034)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051
[2] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, (Internal Report (1990), School of Computer Science, Carnegie Mellon University) · Zbl 0755.90039
[3] Bazaraa, M. S.; Goode, J. J., A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality, European Journal of Operational Research, 3, 322-328 (1979) · Zbl 0405.90062
[4] Berrada, M.; Stecke, K. E., A branch-and-bound approach for machine load balancing in flexible manufacturing systems, Management Science, 32, 1316-1335 (1986) · Zbl 0604.90067
[5] Blazewicz, J., Solving the resource constrained deadline scheduling problem via reduction to the network flow problem, European Journal of Operational Research, 6, 75-79 (1981) · Zbl 0449.90053
[6] Bona, B.; Brandimarte, P.; Greco, C.; Menga, G., Hybrid hierarchical scheduling and control systems in manufacturing, IEEE Transactions on Robotics and Automation, 6, 673-686 (1990)
[7] Booch, G., Object Oriented Design with Application (1991), Benjamin/Cummings: Benjamin/Cummings Menlo Park, CA
[8] Brucker, P.; Jurish, B.; Sievers, B., A fast branch & bound algorithm for the job-shop scheduling problem, (Internal Report 136 (1991), Fachbereich Mathematik/Informatik, Universität Osnabrück)
[9] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Science, 35, 164-176 (1989) · Zbl 0677.90036
[10] Conterno, R.; Ho, Y. C., Order scheduling problem in manufacturing systems, International Journal of Production Research, 26, 1487-1510 (1988) · Zbl 0671.90029
[11] Conterno, R.; Menga, G.; Villa, A., Hierarchical and decentralized approach for batch and repetitive manufacturing, (Proc. IEEE Int. Conf. Robotics and Automation (1987)), 1855-1860
[12] Della Croce, F.; Tadei, R.; Volta, G., A genetic algorithm for the job-shop problem, Computers and Operations Research (1992), to appear in
[13] HOOD reference manual, ESA WME/89-353JB (1989)
[14] Fischer, M. L., Optimal solution of scheduling problems using Lagrange multipliers, part I, Operations Research, 21, 1114-1127 (1973) · Zbl 0294.90085
[15] Fischer, M. L., The Lagrangian relaxation for solving integer programming problems, Management Science, 27, 1-18 (1981) · Zbl 0466.90054
[16] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[17] Geoffrion, A. M., Lagrangian relaxation and its uses in integer programming, Mathematical Programming Study, 2, 82-114 (1974)
[18] Hariri, A. M.A.; Potts, C. M., An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discrete Applied Mathematics, 5, 99-109 (1983) · Zbl 0498.90044
[19] Hariri, A. M.A.; Potts, C. M., Algorithms for two-machine flow-shop sequencing with precedence constraints, European Journal of Operational Research, 17, 238-248 (1984) · Zbl 0551.90041
[20] Held, G., Object Oriented Design with Application (1991), Benjamin/Cummings: Benjamin/Cummings Menlo Park, CA
[21] Hoitomt, D. J.; Luh, P. B.; Max, E.; Pattipati, K. R., Scheduling jobs with simple precedence constraints on parallel machines, Control Systems Magazine, 10, 34-40 (1990)
[22] Hoitomt, D. J.; Luh, P. B.; Pattipati, K. R., Job shop scheduling, (First International Conference on Automation Technology. First International Conference on Automation Technology, Taipei, Taiwan (1990)), 565-574
[23] Lawler, E. L.; Lenstra, J. K.; Rinooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory (1993), North-Holland: North-Holland Amsterdam), to appear in
[24] Lenstra, J. K.; Shmoys, D. M.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46, 259-271 (1990) · Zbl 0715.90063
[25] Luh, P. B.; Hoitomt, D. J.; Max, E.; Pattipati, K. R., Parallel machine scheduling using Lagrangian relaxation, (Proc. Int. Conf. C.I.M. (1988)), 244-248
[26] Luh, P. B.; Hoitomt, D. J.; Max, E.; Pattipati, K. R., Schedule generation and reconfiguration for parallel machines, (Proc. IEEE Int. Conf. Robotics and Automation (1989)), 528-533
[27] Menga, G.; Elia, G.; Mancin, M., G++ an environment for object oriented design and prototyping of manufacturing system, (Programming Environment for C.I.M., Series in Advanced Manufacturing (1991), Springer-Verlag: Springer-Verlag Berlin)
[28] Minoux, M., Mathematical Programming: Theory and Algorithms (1986), Wiley: Wiley New York · Zbl 0602.90090
[29] Pierre, D. A.; Lowe, M. J., Mathematical Programming via Augmented Lagrangians (1975), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0347.90048
[30] Potts, C. M., Lagrangian based branch-and-bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time, Management Science, 31, 1300-1311 (1985) · Zbl 0601.90083
[31] Potts, C. M.; van Wassenhove, L. N., A branch-and-bound algorithm for the total weighted tardiness problem, Operations Research, 33, 363-377 (1985) · Zbl 0566.90046
[32] Shapiro, J. F., A survey of the Lagrangian technique for discrete optimization, Annals of Discrete Mathematics, 5, 113-138 (1974)
[33] van de Velde, S., Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation, Annals of Operations Research, 26, 257-268 (1990) · Zbl 0709.90060
[34] van de Velde, S., Machine scheduling and Lagrangian relaxation, Ph.D. Thesis, University of Eindhoven (1991) · Zbl 0728.90046
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.