Ordering the cases in a workflow can result in significant decrease on the number of late jobs. But merging workflow and scheduling is not trivial. This paper presents some of the problems of using scheduling results in ordering cases in a workflow and tackles two of them: the uncertainties on the cases' processing times and routing. A new approach to modeling these uncertainties is also proposed: the guess and solve technique. It consists of making a guess on the execution times and routes the case will follow, and solving the corresponding deterministic scheduling problem using a suitable technique, in this paper genetic algorithms. Simulation results show that for almost all workloads rules such as earliest due date first, and guess and solve (if the error in guessing is bound by 30%) are statistically significantly better than the commonly used FIFO rule regarding the number of late jobs.2 13961403Bierwirth, C., Kopfer, H., Mattfeld, D.C., Rixen, I., Genetic algorithm based scheduling in a dynamic manufacturing environment (1995) Proc. of 1995 IEEE Conf. on Evolutionary Computation, , Piscataway, NJ. IEEE PressBierwirth, C., Mattfeld, D.C., Minimizing job tardiness: Priority rules vs. adaptative scheduling (1998) Adaptative Computing in Design and Manufacture, , In Ian C. Parmee (ed.), London. Springer-VerlagBierwirth, C., Mattfeld, D.C., Production scheduling and rescheduling with genetic algorithms (1999) Evolutionary Computation, 7, pp. 1-17Cowling, P., Johansson, M., Using real time information for effective dynamic scheduling (2002) European Journal of Operational Research, 139, pp. 230-244França, P.M., Mendes, A., Moscato, P., A memetic algorithm for the total tardiness single machine scheduling problem (2001) European Journal of Operational Research, (132), pp. 224-242Jain, A.S., Meeran, S., A state-of-the-art review of job-shop scheduling techniques (1998) Technical Report, , Department of Applied Physics, Electronic and Mechanical Engineering, University of Dundee, Dundee, ScotlandKendall, E.A., Malkoun, M.T., Jiang, C.H., A methodology for developing agent based systems (1995) First Australian Workshop on Distributed Artificial Intelligence, , In C. Zhang and D. Lukose, editors, Canberra, AustraliaKumar, A., Van der Aalst, W., Verbeek, H., Dynamic work distribution in workflow management systems: How to balance quality and performance? (2001) Journal of Management Information Systems, 18 (3), pp. 157-193Laguna, M., Business Process Modeling, Simulation and Design, , forthcomingMitchell, T.M., (1997) Machine Learning, , McGraw-HillPinedo, M., (1995) Scheduling: Theory, Algorithms and Systems, , Prentice Hall, Englewood Cliffs, New JerseyRaman, N., Talbot, F.B., The job shop tardiness problem: A decomposition approach European Journal of Operational Research, 69, pp. 187-199Reijers, H.A., (2003) Design and Control of Workflow Processes - Business Process Management for the Service Industry, , Springer-Ver lag, BerlinVan der Aalst, W., Van Hee, K., (2002) Workflow Management: Models, Methods and Systems, , The MIT Press - Massachussets Institute of TechnologyZhao, J.L., Stohr, E.A., Temporal workflow management in a claim handling system Proceedings of the International Joint Conference on Work, pp. 187-195. , activities coordination and collaboration, New York, NY, USA. ACM Press