A branch and bound for single machine stochastic scheduling to minimize the maximum lateness

Abstract: This paper studies the problem of single machine stochastic scheduling with random processing times, deterministic due dates and an independent setup time. The jobs are also deteriorated based on the position, which their processes are done. The objective function is to find a schedule of jobs, which minimizes the expected value of maximum lateness. A branch and bound scheme is presented to solve the problem analytically and a simulated annealing meta-heuristic (SA) is also provided for solving the problem in larger scales. Computational experiments demonstrate that the proposed SA is capable of finding near optimal solutions with very low gap.

How to cite this paper

 Haddad, H., Arbabian, M & Pour, K. (2012). A branch and bound for single machine stochastic scheduling to minimize the maximum lateness.International Journal of Industrial Engineering Computations , 3(3), 499-510.

Refrences

Balut, S. (1973). Scheduling to minimize the number of late jobs when set-up and processing times are uncertain. Management Science, 19, 1283–1288.

Cai, X., & Zhou, S. (1997). Scheduling stochastic jobs with asymmetric earliness and tardiness penalties. Naval Research Logistics, 44, 531–557.

Chang, C., & Yao, D. (1993). Rearrangement, majorization and stochastic scheduling. Mathematics of Operations Research, 18, 658–684.

Cheng, T. (1986). Optimal due-date assignment for a single machine sequencing problem with random processing times. International Journal of Systems Science, 17, 1039-1144.

Cheng, T. (1991). Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine. European Journal of Operational Research, 51, 348-353.

De, P., Ghosh, E., & Wells, E. (1991). On the minimization of the weighted number of tardy jobs with random processing times and deadline. Computers and Operations Research, 18, 457–463.

Gutjahr ,W., & Pflug, G. (1996). Simulated annealing for noisy cost functions. Journal of Global Optimization, 8, 1-13.

Gutjahr, W., Hellmayr, A., & Pflug, G. (1999). Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound. European Journal of Operational Research, 117, 396-413.

Jang, W. (2002). Dynamic scheduling of stochastic jobs on a single machine. European Journal of Operational Research, 138, 518–530.

Norkin, I., Ermoliev, Y., & Ruszczynski, A. (1994.). On optimal allocations of indivisibles under uncertainty. Austria: Laxenburg.

Pinedo, M. (1983). Stochastic scheduling with release dates and due dates. Operations Research, 31, 559–572.

Portougal, V., & Trietsch, D. (2006). Setting due dates in a stochastic single machine environment. Computers & Operations Research, 33, 1681–1694.

Sarin S. C, Erel, E., Steiner, G. (1991). Sequencing jobs on a single machine with a common due dates and stochastic processing times. European Journal of Operational Research, 51, 188–198.

Seo, D., Klein, C., & Jang, W. (2005). Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models. Computers & Industrial Engineering, 48, 153–161.

Soroush, H., & Fredendall, L. (1994). The stochastic single machine scheduling problem with earliness and tardiness costs. European Journal of Operational Research, 77, 287–302.

Soroush, H. (2007). Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem. European Journal of Operational Research, 181, 266–287.

Soroush, H., (2010). Solving a stochastic single machine problem with initial idle time and quadratic objective. Computers & Operations Research, 37, 1328–1347.

Soroush, H., (1999). Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs. European Journal of Operational Research, 113, 450-468.

Van Laarhoven, P., & Aarts, E,H.(1988). Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht.