A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system

Abstract: This study investigates minimizing the number of weighted tardy jobs on a single machine when jobs are delivered to either customers or next station in various size batches. In real world, this issue may happen within a supply chain in which delivering goods to customers entails costs. Under such circumstances, keeping completed jobs to deliver in batches may result in reducing delivery costs; nevertheless, it may add to the tardy jobs, which in turn leads to higher costs. In literature review, minimizing the number of weighted tardy jobs is known as NP-Hard problem, so the present issue aiming at minimizing the costs of delivering, in addition to the aforementioned objective function, remains an NP-Hard problem. In this study, the issue is assessed where the customers are numerous, and a mathematical model is presented. We also present a meta-heuristic method based on simulated annealing (SA) and the performance of the SA is examined versus exact solutions.

How to cite this paper

 Mazdeha, M., Hamidinia, A & Karamouzian, A. (2011). A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system.International Journal of Industrial Engineering Computations , 2(3), 491-498.

Refrences

Carlier, J. (1981). Probleme a une machine et algorithmes polynomiaux, Questio 5 (4).

Carlier, J. (1984). Problemes d’ordonnancements a contraintesde ressources: Algorithmes et complexite, These d’EEtat, Ph.D. Thesis, University of Paris VI.

Cerny, V. (1985). A thermodynamic approach to the traveling salesman problem: An efficient simulation. Journal of Optimization: Theory and Applications. 45, 41-51.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5, 287–326.

Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: Batching and delivery. Operations Research, 51 (4) 566–584.

Hallah, R. M., & Bulfin, R. L. (2003). Minimizing the weighted number of tardy jobs on a single machine. European Journal of Operational Research, 145, 45–56.

Karp, R. M. (1972). Reducibility among combinatorial problems, in: Miller, R.E., Thatcher, J.W. (Eds.), Complexity of Computer Computations. Plenum Press, New York, 85–103.

Kirkpatrick, S., Gelett, C. D. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 621-630.

Lenstra, J. K., Rinnooy Kan, A.H.G., & Brucker, P. (1977). Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343–362.

Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore–Hodgson algorithm and the tower of sets property. Mathematical Computer Modeling, 20, 91–106.

Lawler, E. L. (1990). A dynamic programming algorithm for the preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26, 125–133.

Mason, A. J. & Anderson, E. J. (1991). Minimizing flow time on a single-machine with job classes and setup times. Naval Research Logistics, 38, 333–350.

Mahdavi-Mazdeh, M., Sarhadi, M., & Hindi, K. S. (2007). A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs. European Journal of Operational Research, 183, 74–86.

Mahdavi-Mazdeha, M., Sarhadia, M., Hindi, K. S. (2008). A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times. Computers & Operations Research, 35, 1099 – 1111.

Moore, J. M. (1968). An n job one machine algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.

Potts, C. N. & Kovalyov, M. Y. (2000). Scheduling with batching: A review, European Journal of Operational Research, 120, 228–249.

Potts, C. N., & Van Wassenhove, L.N. (1988). Algorithms for scheduling a single machine to minimize the weighted number of late jobs, Management Science, 34, 843–858.

Tang, G. (1990). A new branch and bound algorithm for minimizing the weighted number of tardy jobs, Annals of Operations Research, 24, 225–232.

Villarreal, F. J., & Bulfin, R. L. (1983). Scheduling a single machine to minimize the weighted number of tardy jobs. IIE Transactions, 15, 337–343.