Abstract
In this paper, we consider the integrated planning and scheduling problem on parallel and identical machines. The problem is composed by two parts which are simultaneously solved in an integrated form. The first is the planning part, which consists in determining the jobs that should be processed in each period of time. The second is the scheduling part, which consists in assigning the jobs to the machines according to their release dates. We present new optimization approaches based on local search heuristics and metaheuristic methods based on variable neighborhood search using two neighborhood structures. Two different algorithms were implemented in the construction of initial solutions and combined with fifteen variants of the initial sequence of jobs. Computational experiments were performed with benchmark instances from the literature in order to assess the proposed methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baldea, M., Harjunkoski, I.: Integrated production scheduling and process control: a systematic review. Comput. Chem. Eng. 71, 377–390 (2014)
Chang, Y., Lee, C.: Machine scheduling with job delivery coordination. Eur. J. Oper. Res. 158, 470–487 (2004)
Coffman, E., Garey, M., Johnson, D.: An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7, 1–17 (1978)
Garey, M., Johnson, D.: Strong NP-completeness results: motivation, examples, and implications. J. ACM 25, 499–508 (1978)
Geismar, H., Laporte, G., Lei, L., Sriskandarajah, C.: The integrated production and transportation scheduling problem for a product with a short lifespan. INFORMS J. Comput. 20, 21–33 (2008)
Grossmann, I.: Research challenges in planning and scheduling for enterprise-wide optimization of process industries. In: 10th International Symposium on Process Systems Engineering: Part A, vol. 27, pp. 15–21 (2009)
Jain, A., Meeran, S.: Deterministic job-shop scheduling: past, present and future. Eur. J. Oper. Res. 113, 390–434 (1999)
Kis, T., Kovács, A.: A cutting plane approach for integrated planning and scheduling. Comput. Oper. Res. 39, 320–327 (2012)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997)
Rietz, J., Alves, C., Carvalho, J.V.: Fast heuristics for integrated planning and scheduling. In: Gervasi, O., Murgante, B., Misra, S., Gavrilova, M.L., Rocha, A.M.A.C., Torre, C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2015. LNCS, vol. 9156, pp. 413–428. Springer, Cham (2015). doi:10.1007/978-3-319-21407-8_30
Rietz, J., Alves, C., Braga, N., Carvalho, J.: An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling. Comput. Oper. Res. 76, 183–194 (2016)
Shen, W., Wang, L., Hao, Q.: Agent-based distributed manufacturing process planning and scheduling: a state-of-the-art survey. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 36, 563–577 (2006)
Shobrys, D., White, D.: Planning, scheduling and control systems: why can they not work together. Comput. Chem. Eng. 24, 163–173 (2000)
Sugimori, Y., Kusunoki, K., Cho, F., Uchikawa, S.: Toyota production system and kanban system materialization of just-in-time and respect-for-human system. Int. J. Prod. Res. 15, 553–564 (1977)
Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Acknowledgements
This work has been supported by COMPETE: POCI-01-0145-FEDER-007043 and FCT – Fundação para a Ciência e Tecnologia within the Project Scope: UID/CEC/00319/2013.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Leite, M., Alves, C., Pinto, T. (2017). Variable Neighborhood Search for Integrated Planning and Scheduling. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2017. ICCSA 2017. Lecture Notes in Computer Science(), vol 10405. Springer, Cham. https://doi.org/10.1007/978-3-319-62395-5_49
Download citation
DOI: https://doi.org/10.1007/978-3-319-62395-5_49
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62394-8
Online ISBN: 978-3-319-62395-5
eBook Packages: Computer ScienceComputer Science (R0)