Artículos de revistas
Scheduling Projects With Labor Constraints
Discrete Applied Mathematics. , v. 112, n. 1-3, p. 27 - 52, 2001.
Carvalho De Souza C.
In this paper we consider a labor constrained scheduling problem (LCSP) which is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labor requirement varies as the job is processed. Given the amount of labor available in each period, the problem is to finish all the jobs as soon as possible, that is, to minimize the makespan, subject to the precedence and labor constraints. Several integer programming (IP) formulations for this problem are discussed and valid inequalities for these different models are introduced. It turns out that a major drawback in using an IP approach is the weakness of the lower bound relaxations. However, we report computational experiments showing how the solution of the linear relaxation of the IP models can be used to provide good schedules. Solutions arising from these LP-based heuristics are considerably improved by local search procedures. We further exploit the capabilities of local search for LCSP by designing a Tabu search algorithm. The computational experiments on a benchmark data set show that the Tabu search algorithm generates the best-known upper bounds for almost all these instances. We also show how IP can be used to provide reasonably good lower bounds for LCSP when the makespan is replaced by suitably modified objective functions. Finally, some directions for further investigations which may turn IP techniques into a more interesting tool for solving such a problem are suggested. © 2001 Elsevier Science B.V.1121-32752Aarts, E., Lenstra, J.K., (1997) Local Search in Combinatorial Optimization, , Chichester: WileyAndreatta, G., Brunetta, L., Guastalla, G., (1988) From Ground Holding to Free Flight: A New Exact Approach, , Technical Report, Department of Pure and Applied Mathematics, University of Padova, ItalyBaker, K.R., (1974) Introduction to Sequencing and Scheduling, , New York: WileyCavalcante, C.C.M.B., (1998) Escalonamento Com Restrição de Mão-de-obra: Heurísticas Combinatórias e Limitantes Inferiores, , M.Sc. Dissertation, Instituto de Computação. Universidade Estadual de Campinas (UNICAMP), SP, Brazil (in Portuguese)Heipcke, S., Colombani, Y., Cavalcante, C.C.B.M., De Souza, C.C., Scheduling under labour resource constraints (2000) Constraints, 5, pp. 415-422Glover, F., Tabu search - Part I (1989) ORSA J. Comput., 1, pp. 190-206Glover, F., Tabu search - Part II (1990) ORSA J. Comput., 2, pp. 4-32Glover, F., Laguna, M., Tabu search (1995) Modern Heuristic Techniques for Combinatorial Problems, pp. 70-150. , C.R. Reeves. New York: WileyGoemans, M.X., Improved approximation algorithms for scheduling with release dates (1997) Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, pp. 591-598Gröflin, H., Liebling, T., Connected and alternating vectors: Polyhedra and algorithms (1981) Math. Programming, 20, pp. 233-244Heipcke, S., (1995) Resource Constrained Job-shop Scheduling with Constraint Nets - Two Case Studies, , Diploma Thesis, Mathematisch Geographische Fakultaet, Katholische Universitaet EichstaettHeipcke, S., Colombani, Y., A new constraint programming approach to large scale resource constrained scheduling (1997) Workshop on Models and Algorithms for Planning and Scheduling Problems, , Cambridge, UKHeipcke, S., Colombani, Y., (1997) Solving RCPSPs with SchedEns-Work-in-Progress Report, , School of Business, University of Buckinghamhttp://www.dcc.unicamp.br/~cris/SPLC.htmlNemhauser, G.L., Savelsbergh, M.W.P., Sigismondi, G.C., MINTO, a mixed integer optimizer (1994) Oper. Res. Lett., 15, pp. 47-58Patterson, J.H., A comparison of exact approaches for solving the multiple constrained resource project scheduling problem (1984) Manage. Sci., 30, pp. 854-867Pritsker, A.B., Watters, L.J., Wolfe, P.M., Multiproject scheduling with limited resources: A zero-one programming approach (1969) Manage. Sci., 16, pp. 93-99Rayward-Smith, V.J., Osman, I.H., Reeves, C.R., Smith, G.D., (1996) Modern Heuristic Search Methods, , New York: WileyReeves, C., (1993) Modern Heuristic Techniques for Combinatorial Problems, , New York: WileySavelsbergh, M.W.P., Uma, R.N., Wein, J., An experimental study of LP-based approximation algorithms for scheduling problems (1998) Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 453-462Schulz, A., Skutella, M., Scheduling LPs bear probabilities: Randomized approximations for min-sum criteria (1997) Proceedings of the 1997 European Symposium on Algorithms, pp. 416-429Sousa, J., Wolsey, L.A., Time-indexed formulations of non-preemptive single machine scheduling problems (1992) Math. Programming, 54, pp. 353-367Van Den Akker, M., (1994) LP-based Solution Methods for Single-machine Scheduling Problems, , Ph.D. Thesis, Technical University of EindhovenVan Den Akker, M., Hurkens, C.A.J., Savelsbergh, M.W.P., Time-indexed formulations for machine scheduling problems: Column generation (2000) INFORMS J. on Computing, 12, pp. 111-124Wagner, H.M., Principles of Operations Research (1969) Exercise, 50, p. 502. , Prentice-Hall, Englewood CliffsWolsey, L.A., MIP modelling of changeovers in production planning and scheduling problems (1997) European J. Oper. Res., 99, pp. 154-165Wolsey, L.A., (1998) Integer Programming, , New York: Wiley