Abstract
We consider a job selection problem in a two-stage flow shop. The objective is to select the best job subset with a given cardinality to minimize the makespan. This problem is known to be ordinary \(NP\)-hard and the current state of the art algorithms can solve instances with up to \(3000\) jobs. We introduce a constraint generation approach to the integer linear programming (ILP) formulation of the problem according to which the constraints associated with nearly all potential critical paths are relaxed and then only the ones violated by the relaxed solution are sequentially reinstated. This approach yields a new solution algorithm capable of solving problems with up to \(100000\) jobs or more.
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
Baptiste, P., Della Croce, F., Grosso, A., Tkindt, V.: Sequencing a single machine with due dates and deadlines: an ILP-based approach to solve very large instances. J. Sched. 13, 39–47 (2010)
Ben-Ameur, W., Neto, J.: A constraint generation algorithm for large scale linear programs using multiple-points separation. Math. Program. A 107, 517–537 (2006)
Della Croce, F., Gupta, J.N.D., Tadei, R.: Minimizing tardy jobs in a flowshop with common due date. Eur. J. Oper. Res. 120, 375–381 (2000)
Johnson, S.: Optimal two and three stage production schedules with set-up time included. Nav. Res. Logist. Q. 1, 61–68 (1954)
Jozefowska, J., Jurisch, B., Kubiak, W.: Scheduling shops to minimize the weighted number of late jobs. Oper. Res. Lett. 16, 277–283 (1994)
Junger, M., Reinelt, G., Thienel, S.: Practical problem solving with cutting plane algorithms in combinatorial optimization. In: Cook, W., Lovasz, L., Seymour, P. (eds.) Combinatorial Optimization. DIMACS series in discrete mathematics and theoretical computer science, pp. 111–152. American Mathematical Society, Providence (1995)
Panwalkar, S.S., Koulamas, C.P.: An algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines. Eur. J. Oper. Res. 211, 7–13 (2012)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16, 3–28 (2013)
Tkindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Heidelberg (2002)
Tkindt, V., Della Croce, F., Bouquard, J.L.: Enumeration of Pareto optima for a flow shop scheduling problem with two criteria. INFORMS J. Comput. 19, 64–72 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Della Croce, F., Koulamas, C., T’kindt, V. (2014). A Constraint Generation Approach for the Two-Machine Flow Shop Problem with Jobs Selection. In: Fouilhoux, P., Gouveia, L., Mahjoub, A., Paschos, V. (eds) Combinatorial Optimization. ISCO 2014. Lecture Notes in Computer Science(), vol 8596. Springer, Cham. https://doi.org/10.1007/978-3-319-09174-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-09174-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09173-0
Online ISBN: 978-3-319-09174-7
eBook Packages: Computer ScienceComputer Science (R0)