An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine

Document Type : Research Paper

Authors

1 Faculty of Engineering, University of Isfahan, Isfahan, Iran.

2 Department of Industrial and Systems Engineering, Isfahan University of Technology

Abstract

This paper addresses the Tardy/Lost penalty minimization with common due dates on a single machine. According to this performance measure, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. Initially, we present a 2-approximation algorithm and examine its worst case ratio bound. Then, a pseudo-polynomial dynamic programming algorithm is developed. We show how to transform the dynamic programming algorithm to an FPTAS using the technique of "structuring the execution of an algorithm" and examine the time complexity of our FPTAS.

Keywords

Main Subjects


ALMINANA, M., ESCUDERO, L. F., LANDETE, M., MONGE, J. F., RABASA, A. & SSANCHEZ-SORIANO, J. 2010. A DSS for water irrigation scheduling. Omega, 38, 492-500.
BAPTISTE, P. &SADYKOV, R. 2009. On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation. Naval Research Logistics, 56, 487-502.
BLAZEWICZ, J. 1984. Scheduling preemptible tasks on parallel processors with information loss. Technique et Science Informatiques, 3, 415-420.
BLAZEWICZ, J., PESCH, E., STERNA, M. & WERNER, F. 2004. Open shop scheduling problems with late work criteria. Discrete Applied Mathematics, 134, 1-24.
BLAZEWICZ, J., PESCH, E., STERNA, M. & WERNER, F. 2008. Methaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. Computers and Operations Research, 35, 574-599.
CHEN, B., POTTS, C. N. & WOEGINGER, G. J. 1998. A review of machine scheduling. In: DU, D. Z. & PARDALOS, P. M. (eds.) Handbook of  combinatorial optimization. Boston: Kluwer Academic Publishers.
ENGELS, D. W., KARGER, D. R., KOLLIOPOULOS, S. G., SENGUPTA, S., UMA, R. N. & WEIN, J. 2003. Techniques for Scheduling with Rejection. Journal of Algorithms, 49, 175-191.
FEDERGRUEN, A. & MOSHEIOV, G. 1994. Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs. Operations Research Letters, 16, 199-208.
IBARRA, O. & KIM, C. E. 1875. Fast approximation algorithms for the knapsack and sum of subset problems. problems, Journal of the ACM, 22, 463 468.
JI, M. & CHENG, T. C. E. 2010. Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan. European Journal of Operational Research, 202, 90-98.
KACEM, I. & MAHJOUB, A. R. 2009. Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval. Computers and Industrial Engineering, 56, 1708-1712.
KAHLBACHER, H. G. 1993. Scheduling with monotonous earliness and tardiness penalties. European Journal of Operational Research, 64, 258-277.
KATHLEY, R. B. & ALIDAEE, B. 2002. Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms. Computers and Industrial Engineering, 43, 509-528.
KIANFAR, K. & MOSLEHI, G. 2013. A note on ‘‘Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date’’. Discrete Applied Mathematics, 161, 2205-2206.
LAWLER, E. L. 1964. On scheduling problems with deferral costs. management Science, 11, 280-288.
LEUNG, J. Y. T. 2004. Minimizing total weighted error for imprecise computation tasks and related problems. In: LEUNG, J. Y. T. (ed.) Handbook of scheduling: algorithms, models and performance analysis. Boca Raton: CRC Press.
MOSLEHI, G. & KIANFAR, K. 2014. Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty. Journal of Applied Mathematics.
PESCH, E. & STERNA, M. 2009. Late work minimization in flow shop by a gegnetic algorithm. Computers and Industrial Engineering, 57, 1202-1209.
PINEDO, M. 1995. Scheduling: theory, algorithms and systems, New Jersey, Prentice Hall.
POTTS, C. N. & VAV WASSENHOVE, L. N. 1992a. Approximation algorithms for schrduling a single machine to minimize total late work. Operations Research Letters, 11, 261-266.
POTTS, C. N. & VAV WASSENHOVE, L. N. 1992b. Single machine scheduling to minimize total late work. Operations Research, 40, 586-595.
REN, J., ZHANG, Y. & SUN, J. 2009. The NP-hardness of minimizing the total late workk on an unbounded batch machine. Asia-Pacific Journal of Operational Research, 26, 351-363.
SHABTAY, D. 2008. Due date assignment and scheduling a single machine with a general earliness/tardiness cost function. Computers and Operations Research, 35, 1539-1545.
SHABTAY, D. & BENSOUSSAN, Y. 2010. Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems. Journal of Scheduling, 15, 39-47.
SHABTAY, D., BENSOUSSAN, Y. & KASPI, M. 2012. A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system. International Journal of Production Economics, 136, 67-74.
SHABTAY, D., GASPAR, N. & KASPI, M. 2013. A survey on offline scheduling with rejection. Journal of Scheduling, 16, 3-28.
SLOTNICK, S. A. 2011. Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research, 212, 1-11.
STEINER, G. & ZHANG, R. 2009. Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains. Journal of Scheduling, 12, 565-574.
STERNA, M. 2000. Problems and algorithms in non-classical shop scheduling, Poznan, Scientific Publishers ofthe Polish Academy of Sciences.
STERNA, M. 2006. Late work scheduling in shop systems. Posnan University of Technology.
STERNA, M. 2007a. Dominancec relations for two-machine flow-shop problem with late work criterion. Bulletin of the Polish Academy of Sciences, 55, 59-69.
STERNA, M. 2007b. Late work minimization in a small flexible manufacturing system. Computers and Industrial Engineering, 52, 210-228.
STERNA, M. 2011. A survey of scheduling problems with late work criteria. Omega, 39, 120-129.
VENTURA, J. A. & RAHHAKRISHNAN, S. 2003. Single machine scheduling with symmetric earliness and tardiness penalties. European Journal of Operational Research, 144, 598-612.
WOEGINGER, G. J. 2000. When does a dynamic programming formulation guarantee the existence of an FPTAS? INFORMS Journal on Computing, 12, 57-74.
YUAN, J. 1992. The NP-hardness of the single machine common due date weighted tardiness problem. Systems Science and Mathematical Sciences, 5, 328-333.
ZHOU, X. & CAI, X. 1997. General stochastic single-machine scheduling with regular cost functions. Mathematical and Computer Modelling, 26, 95-108.