Artículos de revistas
Parallel Cooperative Approaches For The Labor Constrained Scheduling Problem
Registro en:
Operations Research/ Computer Science Interfaces Series. , v. 15, n. , p. 201 - 225, 2002.
1387666X
10.1007/978-1-4615-1507-4
2-s2.0-84888808000
Autor
Cavalcante C.C.B.
Cavalcante V.F.
Ribeiro C.C.
de Souza C.C.
Institución
Resumen
In this paper we consider the labor constrained scheduling problem (LCSP), in which a set of jobs to be processed is subject to precedence and labor requirement constraints. Each job has a specified processing time and a labor requirements profile, which typically varies as the job is processed. Given the amount of labor available at each period, the problem consists in determining starting times so as to minimize the overall makespan, subject to the precedence and labor constraints. We propose two parallel cooperative algorithms for LCSP: an asynchronous team and a parallel tabu search strategy. Both algorithms make use of cooperative processes that asynchronously exchange information gathered along their execution. Computational experiments on benchmark instances show that these parallel algorithms produce significantly better solutions than all sequential algorithms previously proposed in the literature. © 2002 by Springer Science+Business Media New York. 15
201 225 Aiex, R.M., Martins, S.L., Ribeiro, C.C., Rodriguez, N.R., Cooperative Multi-Thread Paralell Tabu Search with an Application to Circuit Partitioning (1998) Lecture Notes In Computer Science, 1457, pp. 310-331 Baerentzen, L., Avila, P., Talukdar, S., Learning Network Design for Asynchronous Teams (1997) Lecture Notes In Artificial Intelligence, 1237, pp. 177-196 Baker, K.R., (1974) Introduction to Sequencing and Scheduling, , Wiley Cavalcante, C.B., Colombani, Y., Heipcke, S., Souza, C.C., Scheduling under Labour Resource Constraints (2000) Constraints, 5, pp. 415-422 Cavalcante, C.B., Souza, C.C., (1997) A Tabu Search Approach For Scheduling Problem Under Labour Constraints, , Technical Report, State University of Campinas, Institute of Computing, IC-97-13 Cavalcante, C.B., Souza, C.C., Savelsbergh, M.W., Wang, Y., Wolsey, L.A., Scheduling Projects with Labor Constraints To appear in: Discrete Applied Mathematics Cavalcante, V.F., (1995) Asynchronous Teams For the Job Shop Scheduling Problem: Construction Heuristic (in Portuguese), , M.Sc. Dissertation, State University of Campinas, Institute of Computing Cavalcante, C.C.B., (1998) Scheduling Under Labour Constraints: Heuristics and Lower Bounds (in Portuguese), , M.Sc. Dissertation, State University of Campinas, Institute of Computing Chakaprani, J., Skorin-Kapov, J., Massively Parallel Tabu Search for the Quadratic Assignment Problem (1993) Annals of Operations Research, 41, pp. 327-341 Chakaprani, J., Skorin-Kapov, J., Connection Machine Implementation of a Tabu Search for the Traveling Salesman Problem (1993) Journal of Computing and Information Technology, 1, pp. 29-36 Chang, P., Dolan, J., Hemmerle, J., Talukdar, S., Terk, M., Asynchronous Teams: An Agent-Based Problem-Solving Architecture (1997) Artificial Neural Networks In Engineering, 7, pp. 73-78 Crainic, T.G., Toulouse, M., Gendreau, M., Parallel Asynchronous Tabu Search for Multicommodity Location-Allocation with Balancing Requirements (1993) Annals of Operations Research, 63, pp. 277-299 Crainic, T.G., Toulouse, M., Gendreau, M., Synchronous Tabu Search Parallelization Strategies for Multicommodity Location-Allocation with Balancing Requirements (1995) OR Spektrum, 17, pp. 113-123 Cung, V.-D., Martins, S.L., Ribeiro, C.C., Roucairol, C., Strategies for the Parallel Implementation of Metaheuristics (2001) Essays and Surveys In Metaheuristics, , C.C. Ribeiro and P. Hansen, editors, Kluwer, this volume Davis, E.W., Patterson, J.H., A Comparison of Heuristics and Optimum Solutions in Resource Constrained Project Scheduling (1975) Management Science, 21, pp. 944-955 Glover, F., Tabu Search - Part I (1989) ORSA Journal On Computing, 1, pp. 190-206 Glover, F., Tabu Search - Part II (1990) ORSA Journal On Computing, 2, pp. 4-32 Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer Haddad, E.G., (1996) Asynchronous Teams For the Job Shop Scheduling Problem: Improvement Heuristics (in Portuguese), , M.Sc. Dissertation, State University of Campinas, Institute of Computing Heipcke, S., (1995) A New Constraint Programming Approach to Large Scale Resource Constrained Scheduling, , Diploma-Thesis, Mathematisch Geographische Fakultat, Katholische Universitat Eichstatt Heipcke, S., Colombani, Y., A New Constraint Programming Approach to Large Scale Resource Constrained Scheduling (1997) Presented At the Workshop On Models and Algorithms For Planning and Scheduling Problems, , Cambridge Patterson, J.H., Project Scheduling: The Effects of Problem Structure on Heuristic Performance (1976) Naval Research Logistics Quaterly, 20, pp. 95-123 Peixoto, H.P., (1995) A Methodology For the Specification of Asynchronous Teams For Combinatorial Optimization Problems (in Portuguese), , M.Sc. Dissertation, State University of Campinas, Institute of Computing Porto, S.C., Ribeiro, C.C., Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints (1996) Journal of Heuristics, 1, pp. 107-223 Rachlin, J., Goodwin, R., Murthy, S., Akkiraju, R., Wu, F., Kumaran, S., Teams, R.D., An Agent Architecture for Optimization and DecisionSupport (1999) Lecture Notes In Artificial Intelligence, 1555, pp. 261-276 Rego, C., Roucairol, C., A Parallel Tabu Search Algorithm using Ejection Chains for the VRP (1996) Metaheuristics: Theory and Applications, pp. 253-295. , I.H. Osman and J.P. Kelly, editors, Kluwer Rochat, Y., Taillard, E.D., Probabilistic Diversification and Intensification in Local Search for Vehicle Routing (1995) Journal of Heuristics, 1, pp. 147-167 Savelsbergh, M.W., Uma, R.N., Wein, J., An Experimental Study ofLPbased Approximation Algorithms for Scheduling Problems (1998) Proceedings of the 9th Annual ACM-SIAM Symposium On Discrete Algorithms, pp. 453-462 Savelsbergh, M.W., Wang, Y., Wolsey, L.A., (1996) Computational Experiments With a Large-Scale Resource Constrained Project Scheduling Problem, , Note, Georgia Institute of Technology Souza, C.C., Wolsey, L.A., (1997) Scheduling Projects With Labour Constraints, , Technical Report, State University of Campinas, Institute of Computing, IC-97-13 Souza, P.S., (1993) Asynchronous Organizations For Multi-Algorithm Problems, , Ph.D. Dissertation, Electrical and Computer Engineering Department, Carnegie Mellon University Souza, P.S., Talukdar, S.N., Genetic Algorithms in Asynchronous Teams (1991) Proceedings of the Fourth International Conference On Genetic Algorithms, pp. 392-397. , Morgan Kaufmann Storer, R.H., Wu, S.D., Vaccari, R., New Search Spaces for Sequence Problems with Applications to Job Shop Scheduling (1992) Management Science, 38, pp. 1495-1509 Taillard, E.D., Robust Taboo Search Techniques for the Quadratic Assignment Problem (1991) Parallel Computing, 17, pp. 443-455 Taillard, E.D., Parallel Taboo Search Techniques for the Job Shop Scheduling Problem (1994) ORSA Journal On Computing, 6, pp. 108-117 Talukdar, S.N., Baerentzen, L., Gove, A., Asynchronous Teams: Cooperation Schemes for Autonomous Agents (1998) Journal of Heuristics, 4, pp. 295-321 Talukdar, S.N., Pyo, S.S., Giras, T., Asynchronous Procedures for Parallel Processing (1983) IEEE Transactions On Power Apparatus and Systems, pp. 3652-3659. , PAS-102 Verhoeven, M.G.A., Aarts, E.H.L., Parallel Local Search (1995) Journal of Heuristics, 1, pp. 43-65