×

An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling. (English) Zbl 1349.90290

Summary: The resolution of planning and scheduling problems in a coordinated way within the supply chain is very challenging. In this paper, we address the integration of medium-term production planning and short-term scheduling models. We particularly focus on a specific problem defined on parallel machines that has recently been explored in the literature. The problem is characterized by a set of jobs that can be processed only from a given release date onward, and which should be finished at a given due date. At a first stage, the problem consists in assigning the jobs to consecutive time periods within the planning horizon, while at a second stage, the jobs have to be scheduled on the available machines. Our contribution consists in the description and analysis of a new detailed scheduling model based on a pseudo-polynomial network flow formulation that can be used to exactly solve real size instances. We explore different strategies to simplify the model and reduce its number of constraints. To evaluate the performance of our approaches, we report an extensive set of computational experiments on benchmark instances from the literature. The results obtained show that our approach outperforms, on some classes of instances, other state-of-the-art methods described recently in the literature.

MSC:

90B30 Production models
90B10 Deterministic network models in operations research
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alves, C.; Valério de Carvalho, J., A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Comput Oper Res, 35, 4, 1315-1328 (2008) · Zbl 1163.90702
[2] Amaro, A.; Barbosa-Póvoa, A., Planning and scheduling of industrial supply chains with reverse flowsa real pharmaceutical case study, Comput Chem Eng, 32, 2606-2625 (2008)
[3] Armstrong, R.; Gao, S.; Lei, L., A 0-inventory production and distribution problem with a fixed customer sequence, Ann Oper Res, 159, 395-414 (2008) · Zbl 1152.90301
[4] Bassett, M.; Pekny, J.; Reklaitis, G., Decomposition techniques for the solution of large-scale scheduling problems, AIChE J, 42, 3373-3387 (1996)
[6] Belov, G.; Scheithauer, G., A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, Eur J Oper Res, 171, 85-106 (2006) · Zbl 1091.90080
[7] Carlier, J.; Néron, E., A new LP-based lower bound for the cumulative scheduling problem, Eur J Oper Res, 127, 363-382 (2000) · Zbl 0990.90036
[8] Chang, Y.; Lee, C., Machine scheduling with job delivery coordination, Eur J Oper Res, 158, 470-487 (2004) · Zbl 1067.90041
[9] Coffman, E.; Garey, M.; Johnson, D., (Hochbaum, D., Approximation algorithms for NP-hard problems (1996), PWS Publishing: PWS Publishing Boston), 46-93, [Chapter 2]
[10] Detienne, B., A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, Eur J Oper Res, 235, 540-552 (2014) · Zbl 1305.90179
[11] Erdirik-Dogan, M.; Grossmann, I., Simultaneous planning and scheduling of single-stage multi-product continuous plants with parallel lines, Comput Chem Eng, 32, 2664-2683 (2008)
[12] Geismar, H.; Laporte, G.; Lei, L.; Sriskandarajah, C., The integrated production and transportation scheduling problem for a product with a short life span and non-instantaneous transp. time, INFORMS J Comput, 20, 21-33 (2008) · Zbl 1243.90023
[13] Grossmann, I.; Furman, K., Challenges in enterprise-wide optimization for the process industries, (Chaovalitwongse, W.; Furman, K.; Pardalos, P., Optimization and logistics challenges in the enterprise (2009), Springer), 3-60 · Zbl 1172.90432
[14] Joly, M.; Moro, L.; Pinto, J., Planning and scheduling for petroleum refineries using mathematical programming, Braz J Chem Eng, 19, 207-228 (2002)
[15] Kis, T.; Kovács, A., A cutting plane approach for integrated planning and scheduling, Comput Oper Res, 39, 320-327 (2012) · Zbl 1251.90158
[16] Li, Z.; Ierapetritou, M., Integrated production planning and scheduling using a decomposition framework, Chem Eng Sci, 64, 3585-3597 (2009)
[17] Maravelias, C., A decomposition framework for the scheduling of single and multi-stage processes, Comput Chem Eng, 30, 407-420 (2006)
[18] Maravelias, C.; Sung, C., Integration of production planning and schedulingoverview, challenges and opportunities, Comput Chem Eng, 33, 1919-1930 (2009)
[19] Roe, B.; Papageorgiou, L.; Shah, N., A hybrid milp/clp algorithm for multipurpose batch process scheduling, Comput Chem Eng, 29, 1277-1291 (2005)
[20] Sadykov, R.; Wolsey, L., Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates, INFORMS J Comput, 18, 2, 209-217 (2006) · Zbl 1241.90056
[21] Scheithauer, G., Zuschnitt- und Packungsoptimierung (2008), Vieweg + Teubner Verlag: Vieweg + Teubner Verlag Wiesbaden · Zbl 1144.90001
[22] Su, L.-H.; Cheng, T.; Chou, F.-H., A minimum-cost network flow approach to preemptive parallel-machine scheduling, Comput Ind Eng, 64, 453-458 (2013)
[23] Sung, C.; Maravelias, C., An attainable region approach for production planning of multi-product processes, AIChE J, 53, 1298-1315 (2007)
[24] Valério de Carvalho, J., Exact solution of bin packing problems using column generation and branch and bound, Ann Oper Res, 86, 629-659 (1999) · Zbl 0922.90113
[25] Vancza, J.; Kis, T.; Kovacs, A., Aggregation the key to integrating production planning and scheduling, CIRP Ann - Manuf Technol, 53, 377-380 (2004)
[26] Wang, X.; Cheng, T., Machine scheduling with an availability constraint and job delivery coordination, Nav Res Logist, 54, 11-20 (2007) · Zbl 1124.90011
[27] Yan, H.; Zhang, X., A case study on integrated production planning and scheduling in a three stage manufacturing system, IEEE Trans Autom Sci Eng, 4, 86-92 (2007)
[28] Yang, H.; Sun, Q.; Saygin, C.; Sun, S., Job shop scheduling based on earliness and tardiness penalties with due dates and deadlinesan enhanced genetic algorithm, Int J Adv Manuf Technol, 61, 657-666 (2012)
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.