Scheduling Projects With Labor Constraints

dc.creatorCavalcante C.C.B.
dc.creatorCarvalho De Souza C.
dc.creatorSavelsbergh M.W.P.
dc.creatorWang Y.
dc.creatorWolsey L.A.
dc.date2001
dc.date2015-06-26T14:44:00Z
dc.date2015-11-26T14:17:36Z
dc.date2015-06-26T14:44:00Z
dc.date2015-11-26T14:17:36Z
dc.date.accessioned2018-03-28T21:18:43Z
dc.date.available2018-03-28T21:18:43Z
dc.identifier
dc.identifierDiscrete Applied Mathematics. , v. 112, n. 1-3, p. 27 - 52, 2001.
dc.identifier0166218X
dc.identifier10.1016/S0166-218X(00)00308-5
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-0345821708&partnerID=40&md5=c25418032d97c444a8a94a2d2ea6e4ef
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/95252
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/95252
dc.identifier2-s2.0-0345821708
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1243383
dc.descriptionIn 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.
dc.description112
dc.description1-3
dc.description27
dc.description52
dc.descriptionAarts, E., Lenstra, J.K., (1997) Local Search in Combinatorial Optimization, , Chichester: Wiley
dc.descriptionAndreatta, 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, Italy
dc.descriptionBaker, K.R., (1974) Introduction to Sequencing and Scheduling, , New York: Wiley
dc.descriptionCavalcante, 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)
dc.descriptionHeipcke, S., Colombani, Y., Cavalcante, C.C.B.M., De Souza, C.C., Scheduling under labour resource constraints (2000) Constraints, 5, pp. 415-422
dc.descriptionGlover, F., Tabu search - Part I (1989) ORSA J. Comput., 1, pp. 190-206
dc.descriptionGlover, F., Tabu search - Part II (1990) ORSA J. Comput., 2, pp. 4-32
dc.descriptionGlover, F., Laguna, M., Tabu search (1995) Modern Heuristic Techniques for Combinatorial Problems, pp. 70-150. , C.R. Reeves. New York: Wiley
dc.descriptionGoemans, M.X., Improved approximation algorithms for scheduling with release dates (1997) Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, pp. 591-598
dc.descriptionGröflin, H., Liebling, T., Connected and alternating vectors: Polyhedra and algorithms (1981) Math. Programming, 20, pp. 233-244
dc.descriptionHeipcke, S., (1995) Resource Constrained Job-shop Scheduling with Constraint Nets - Two Case Studies, , Diploma Thesis, Mathematisch Geographische Fakultaet, Katholische Universitaet Eichstaett
dc.descriptionHeipcke, 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, UK
dc.descriptionHeipcke, S., Colombani, Y., (1997) Solving RCPSPs with SchedEns-Work-in-Progress Report, , School of Business, University of Buckingham
dc.descriptionhttp://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-58
dc.descriptionPatterson, J.H., A comparison of exact approaches for solving the multiple constrained resource project scheduling problem (1984) Manage. Sci., 30, pp. 854-867
dc.descriptionPritsker, A.B., Watters, L.J., Wolfe, P.M., Multiproject scheduling with limited resources: A zero-one programming approach (1969) Manage. Sci., 16, pp. 93-99
dc.descriptionRayward-Smith, V.J., Osman, I.H., Reeves, C.R., Smith, G.D., (1996) Modern Heuristic Search Methods, , New York: Wiley
dc.descriptionReeves, C., (1993) Modern Heuristic Techniques for Combinatorial Problems, , New York: Wiley
dc.descriptionSavelsbergh, 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-462
dc.descriptionSchulz, A., Skutella, M., Scheduling LPs bear probabilities: Randomized approximations for min-sum criteria (1997) Proceedings of the 1997 European Symposium on Algorithms, pp. 416-429
dc.descriptionSousa, J., Wolsey, L.A., Time-indexed formulations of non-preemptive single machine scheduling problems (1992) Math. Programming, 54, pp. 353-367
dc.descriptionVan Den Akker, M., (1994) LP-based Solution Methods for Single-machine Scheduling Problems, , Ph.D. Thesis, Technical University of Eindhoven
dc.descriptionVan 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-124
dc.descriptionWagner, H.M., Principles of Operations Research (1969) Exercise, 50, p. 502. , Prentice-Hall, Englewood Cliffs
dc.descriptionWolsey, L.A., MIP modelling of changeovers in production planning and scheduling problems (1997) European J. Oper. Res., 99, pp. 154-165
dc.descriptionWolsey, L.A., (1998) Integer Programming, , New York: Wiley
dc.languageen
dc.publisher
dc.relationDiscrete Applied Mathematics
dc.rightsfechado
dc.sourceScopus
dc.titleScheduling Projects With Labor Constraints
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución