Parallel-Batch Scheduling with Deterioration and Rejection on a Single Machine

Parallel-Batch Scheduling with Deterioration and Rejection on a Single Machine

Cuixia Miao Fanxiao Meng 

School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China

Corresponding Author Email:,
15 March 2017
15 April 2017
30 March 2017
| Citation



In this paper, we consider the bounded parallel-batch scheduling with deterioration and rejection on a single machine. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on the single machine. The objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the rejected jobs. We analyze the complexity of the problem, present a pseudo-polynomial time algorithm and a fully polynomial-time approximation scheme.


Batch scheduling, deterioration, rejection, pseudo-polynomial time algorithm, fully polynomial-time approximation scheme (FPTAS)

1. Introduction
2. Preliminaries
3. Mainresults
4. Conclusion

1. Y.Bartal, S.Leonardi,A. Marchetti-Spaccamela ,L. Stougie, Multiprocessor scheduling with rejection, ,2000, SIAM Journal of Discrete Mathematics, vol.13, pp.64-78.

2.  P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn, S. van de Velde, Scheduling a batching machine, 1998,   Journal of Scheduling, vol.1, pp. 31-54.

3. S.Browne, U.Yechiali, Scheduling deteriorating jobs on a single processor, 1990, Operations Research, vol.38, no.3, pp. 495-498.

4. T.C.E Cheng, Q. Ding, B.M.T. Lin, A concise survey of scheduling with time-dependent processing times, 2004, European Journal of Operational Research, vol.152, pp.1-13.

5. Y.S. Cheng, S.T. Sun,  Scheduling linear deterirating jobs with rejection on a single machine, 2009,European Journal of Operational Research, vol.194, pp. 18-27.

6. S.Gawiejnowicz, Time-Dependent Scheduling,  2008, Monographs in Theoretical Computer Science An EATCS Series, Berlin-New York, vol18.

7.  G.N.D. Gupta, S.K. Gupta,  Single facility scheduling with nonlinear processing times, 1988, Computer and Ind Engineering, vol.14, pp. 387-393.

8. M. Ji,  T.C.E. Cheng, Parallel machine scheduling of single linear deteriorating jobs, Theoretical Computer Science, vol.410, pp.3761-3768.

9. C.Y. Lee, R. Uzsoy,  L.A. Martin-Vega, Efficient algorithms for scheduling semiconductor burn-in operations, 1992, Operations Research, vol.40, pp.764-775.

10. S.S. Li,  J.J. Yuan,  Single machine parallel-btach scheduling with deteriorating jobs, 2009, Theoretical Computer Science, vol.410, pp. 830-836.

11. M. Liu, F.F. Zheng, C.B. Chu, J.T. Zhang,  An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration, 2012, Journal of Combinatorial Optimization, vol.23, pp. 483-492.

12. G. Mosheiov, Scheduling jobs under simple linear deterioration, 1994, Computers and Operations Research, vol.21, pp.653-659.

13.  C.X. Miao, Y.Z. Zhang, Z.G. Cao, Bounded parallel-batch scheduling on single and multi-machines for deteriorating jobs, 2011, Information Processing Letters, vol.111, pp. 798-803.

14. C.N. Potts, M.Y. Kovalyov, Scheduling with batching: A review, 2000, European Journal of Operational Research, vol. 120, pp.228-249.

15. S. Sengupta, Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection, 2003, LNCS, vol.2748, pp.79-90.

16. G.J. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? 1999,  Proceeding of 10th ACM-SIAM Symposium on discrete Algorithms, pp.820-829.

17. J.J. Yuan, S.S. Li, R.Y. Fu, A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times, 2009, Journal of Combinatorial Optimization, vol.7, pp.206-213.

18. Y.Z. Zhang, C.X. Miao,  Copy method and its applications on the batching scheduling problems, 2004, Journal of Qufu Normal University, vol.2, pp. 41-43. (in Chinese)