×

zbMATH — the first resource for mathematics

A resource constrained scheduling problem with multiple independent producers and a single linking constraint: a coal supply chain example. (English) Zbl 1304.90105
Summary: This paper examines a resource constrained production planning and scheduling problem motivated by the coal supply chain. In this problem, multiple independent producers are connected with a resource availability (or, linking) constraint. A general description of such problems is provided, before decomposing the problem into two levels. In the first level, we deal with production planning and in the second level, we deal with tactical resource scheduling. A real-world coal supply chain example is presented to anchor the approach. The overall problem can be formulated as an integrated mixed integer programming model which, in several cases, struggles to find even a feasible solution in reasonable amount of time. This paper discusses a distributed decision making approach based on column generation (CG). Computational experiments show that, the CG scheme has significant advantages over the integrated model and a Lagrangian relaxation scheme proposed by A.Thomas et al., “Distributed optimisation method for multi-resource constrained scheduling in coal supply chains”, Int. J. Prod. Res. 51, 2740–2759 (2013; doi:10.1080/00207543.2012.737955)]. This paper concludes with detailed discussions on the results and future research directions.

MSC:
90B35 Deterministic scheduling theory in operations research
90B90 Case-oriented studies in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atamtürk, A., Cover and pack inequalities for (mixed) integer programming, Annals of Operations Research, 139, 21-38, (2005) · Zbl 1091.90053
[2] Barahona, F.; Anbil, R., The volume algorithm: producing primal solutions with a subgradient method, Mathematical Programming, 87, 385-399, (2000) · Zbl 0961.90058
[3] Ben Amor, H.; Desrosiers, J.; Frangioni, A., On the choice of explicit stabilizing terms in column generation, Discrete Applied Mathematics, 157, 1167-1184, (2009) · Zbl 1169.90395
[4] Borndorfer, R., Schelten, U., Schlechte, T., & Weider, S. (2005). A column generation approach to airline crew scheduling. Technical Report 05-37 ZIP. · Zbl 1114.90375
[5] Bracken, J.; McGill, J. T., Mathematical programs with optimization problems in the constraints, Operations Research, 21, 37-44, (1973) · Zbl 0263.90029
[6] Brandimarte, P.; Calderini, M., A hierarchical bicriterion approach to integrated process plan selection and job shop scheduling, International Journal of Production Research, 33, 161, (1995) · Zbl 0914.90156
[7] Brucker, P.; Knust, S., Complex scheduling, (2006), Springer-Verlag Berlin, Heidelberg · Zbl 1154.90002
[8] Capone, A.; Carello, G.; Filippini, I.; Gualandi, S.; Malucelli, F., Solving a resource allocation problem in wireless mesh networks: A comparison between a CP-based and a classical column generation, Networks, 55, 221-233, (2010) · Zbl 1200.90038
[9] Choi, E.; Tcha, D.-W., A column generation approach to the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 34, 2080-2095, (2007) · Zbl 1187.90094
[10] Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Operations Research, 8, 101-111, (1960) · Zbl 0093.32806
[11] Desrosiers, J.; Lubbecke, M. E., A primer in column generation, (Desaulniers, G.; Desrosiers, J.; Solomon, M., Column generation, (2005), Springer US), 1-32 · Zbl 1246.90093
[12] Ebadian, M.; Rabbani, M.; Torabi, S. A.; Jolai, F., Hierarchical production planning and scheduling in make-to-order environments: reaching short and reliable delivery dates, International Journal of Production Research, 47, 5761-5789, (2009) · Zbl 1198.90177
[13] Hans, E. W.; Herroelen, W.; Leus, R.; Wullink, G., A hierarchical approach to multi-project planning under uncertainty, Omega, 35, 563-577, (2007)
[14] Huisman, D., Jans, R., Peeters, M., & Wagelmans, A. P. M. (2005). Combining column generation and Lagrangian relaxation. In G. Desaulniers, J. Desrosiers, & M. Solomon (Eds.), Column generation (pp. 247-270). · Zbl 1120.90366
[15] Kelly, J. D.; Zyngier, D., Hierarchical decomposition heuristic for scheduling: coordinated reasoning for decentralized and distributed decision-making problems, Computers and Chemical Engineering, 32, 2684-2705, (2008)
[16] Lenstra, J. K.; Kan, A. H.G. R.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362, (1977) · Zbl 0353.68067
[17] Lubbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 1007-1023, (2005) · Zbl 1165.90578
[18] Pessoa, A.; Uchoa, E.; de Aragao, M. P.; Rodrigues, R., Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Mathematical Programming Computation, 2, 1-32, (2010)
[19] Pochet, Y.; Wolsey, L. A., Production planning by mixed integer programming, (2006), Springer NY · Zbl 1102.90039
[20] Singh, G., Dunstall, S., Eitzen, G., Ernst, A. T., Horn, M., & Krishnamoorthy, M. (2005). On coordination and scheduling in wine supply chains. In 5th International conference on operational research for development (ICORD), Jamshedpur, India (pp. 219-229).
[21] Singh, G.; Sier, D.; Ernst, A. T.; Gavriliouk, O.; Oyston, R.; Giles, T., A mixed integer programming model for long term capacity expansion planning: A case study from the Hunter valley coal chain, European Journal of Operational Research, 220, 210-224, (2012) · Zbl 1253.90157
[22] Thomas, A.; Singh, G.; Krishnamoorthy, M.; Venkateswaran, J., Distributed optimisation method for multi-resource constrained scheduling in coal supply chains, International Journal of Production Research, 51, 2740-2759, (2013)
[23] Timm, T.; Blecken, A., A method for the hierarchical planning of the structure, dimension and material requirements of manufacturing systems, International Journal of Production Research, 49, 3431-3453, (2011)
[24] Vanderbeck, F.; Wolsey, L. A., Reformulation and decomposition of integer programs, (Junger, M.; Liebling, T.; Naddef, D.; Nemhauser, G. L.; Pulleyblank, W. R.; Reinelt, G.; etal., 50 Years of integer programming 1958-2008, (2010), Springer Berlin), 431-504 · Zbl 1187.90207
[25] Wang, G. L.; Lin, L.; Zhong, S. S., Task-oriented hierarchical planning and scheduling for discrete manufacturing enterprise, Applied Mechanics and Materials, 114-120, (2008)
[26] Wedelin, D., An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Annals of Operations Research, 57, 283-301, (1995) · Zbl 0831.90087
[27] Wentges, P., Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming, International Transactions in Operational Research, 4, 151-162, (1997) · Zbl 0886.90107
[28] Wu, D.; Ierapetritou, M., Hierarchical approach for production planning and scheduling under uncertainty, Chemical Engineering and Processing: Process Intensification, 46, 1129-1140, (2007)
[29] Zribi, N.; Kacem, I.; El Kamel, A.; Borne, P., Assignment and scheduling in flexible job-shops by hierarchical optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 37, 652-661, (2007)
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.