[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The single machine serial batch scheduling problems with rejection

  • Original Paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

We consider several serial batch scheduling problems with rejection. Each job is either processed on a single serial batching machine or rejected by paying a penalty. We analyze two models with rejection. The first model is to minimize the sum of the scheduling cost of the accepted jobs and the total penalty of the rejected jobs, where the scheduling costs are the total completion time, the makespan, the maximum lateness and the weighted number of tardy jobs, respectively. For the former two problems, we propose two polynomial time algorithms to solve them. For the last two problems, we derive efficient dynamic programming algorithms. The second model is to minimize the makespan, given an upper bound on the total rejection cost, we present a fully polynomial time approximation scheme.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bartal Y, Leonardi S, Spaccamela AM, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discret Math 13(1):64–78

    Article  Google Scholar 

  • Coffman EG, Yannakakis M, Magazine MJ, Santos C (1990) Batch sizing and sequencing on a single machine. Oper Res 51(4):566–584

    Google Scholar 

  • Engels DW, Karger DR, Kolliopoulos SG, Sengupta S, Uma RN, Wein J (2003) Techniques for scheduling with rejection. J Algorithms 49(1):175–191

    Article  Google Scholar 

  • Guntzer MM, Jungnickel D (2000) Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Oper Res Lett 26(2):55–66

    Article  Google Scholar 

  • Hoogeveen H, Skutella M, Woeginger GJ (2003) Preemptive scheduling with rejection. Math Prog 94(3):361–374

    Article  Google Scholar 

  • Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Plenum Press, New York, pp 85–103

  • Ng CT, Cheng TCE, Yuan JJ, Liu ZH (2003) On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times. Oper Res Lett 31(4):323–326

    Article  Google Scholar 

  • Sengupta S (2003) Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Lect Notes Comput Sci 2748:79–90

    Article  Google Scholar 

  • Shabtay D (2014) The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur J Oper Res 233(1):64–74

    Article  Google Scholar 

  • Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16(3):3–28

    Article  Google Scholar 

  • T’kindt V, Billaut JC (2006) Multicriteria scheduling: theory, models and algorithms. Springer, Berlin

    Google Scholar 

  • Webster S, Baker KR (1995) Scheduling groups of jobs on a single machine. Oper Res 43(4):692–703

    Article  Google Scholar 

  • Xuan H, Li B (2013) Scheduling dynamic hybrid flow shop with serial batching machine. J Oper Res Soc 64(6):825–832

    Article  Google Scholar 

  • Yuan JJ, Yang AF, Cheng TCE (2004) A note on the single machine serial batching scheduling problem to minimize maximum lateness with identical processing times. Eur J Oper Res 158(2):525–528

    Article  Google Scholar 

  • Zhang L, Lu L, Yuan J (2010) Single machine scheduling under the job rejection constraint. Theoret Comput Sci 411(16):1877–1882

    Article  Google Scholar 

Download references

Acknowledgments

The authors thank the anonymous reviewers for their helpful and detailed comments on an earlier version of our paper. This paper is supported by the National Natural Science Foundation of China (11201259) and the Doctoral Fund of the Ministry of Education (20123705120001 & 20123705110003).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong, China

    Juan Zou & Cuixia Miao

Authors
  1. Juan Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cuixia Miao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juan Zou.

Appendix 1: Numerical example

Appendix 1: Numerical example

The following numerical example illustrates Algorithm DP1. (see (Shabtay 2014)). The job processing times and rejection costs are given in below Table, where s = 2.

j

1

2

3

4

5

p j

3

5

6

8

11

e j

15

17

20

28

24

Next, we apply Algorithm DP1 to solve the example.

First, we compute the case h = 1.

$$ \begin{aligned} & j = 5,F\left( {5,0,0,0} \right) = e_{5} = 24,F\left( {5,1,1,1} \right) = p_{5} + s = 13. \\ & j = 4,F\left( {4,0,0,0} \right) = e_{4} + e_{5} = 52, \\ & F\left( {4,1,1,1} \right) = { \hbox{min} }\left\{ {F\left( {5,0,0,0} \right) + \left( {s + p_{4} } \right),F\left( {5,1,1,1} \right) + e_{4} } \right\} = {\text{min }}\left\{ {24 + 10,13 + 28} \right\} = 34. \\ & F\left( {4,2,1,1} \right) = { \hbox{min} }\left\{ {F\left( {5,1,1,1} \right) + 2\left( {s + p_{4} } \right),F\left( {5,2,1,1} \right) + e_{4} } \right\} = { \hbox{min} } \left\{ {13 + 20, \infty } \right\} = 33. \\ & j = 3,F\left( {3, \, 0, \, 0, \, 0} \right) = e_{3} + e_{4} + e_{5} = 72, \\ & F\left( {3,1,1,1} \right) = { \hbox{min} }\left\{ {F\left( {4,0,0,0} \right) + s + p_{3} ,F\left( {4,1,1,1} \right) + e_{3} } \right\} = { \hbox{min} }\left\{ {52 + 8, 34 + 20} \right\} = 54, \\ & F\left( {3,2,1,1} \right) = { \hbox{min} }\left\{ {F\left( {4,1,1,1} \right) + 2\left( {s + p_{3} } \right),F\left( {4,2,1, 1} \right) + e_{3} } \right\} = { \hbox{min} } \left\{ {34 + 16, \, 33 + 20} \right\} = 50, \\ & F\left( {3,3,1,1} \right) = { \hbox{min} } \left\{ {F\left( {4,2,1,1} \right) + 3\left( {s + p_{3} } \right),F\left( {4,3,1,1} \right) + e_{3} } \right\} = { \hbox{min} } \left\{ {33 + 24, \, \infty } \right\} = 57. \\ & j = 2,F\left( {2,0,0,0} \right) = e_{2} + e_{3} + e_{4} + e_{5} = 89, \\ & F(2,1,1,1) = \hbox{min} \{ F(3,0,0,0) + s + p_{2} ,F(3,1,1,1) + e_{2} \} = \hbox{min} \{ 72 + 7,54 + 17\} = 71 \\ & F(2,2,1,1) = \hbox{min} \{ F(3,1,1,1) + 2(s + p_{2} ),F(3,2,1,1) + e_{2} \} = \hbox{min} \{ 54 + 14,50 + 17\} = 67 \\ & F(2,3,1,1) = \hbox{min} \{ F(3,2,1,1) + 3(s + p_{2} ),F(3,3,1,1) + e_{2} \} = \hbox{min} \{ 50 + 21,57 + 17\} = 71 \\ & F\left( {2,4,1,1} \right) = { \hbox{min} }\left\{ {F\left( {3,3,1,1} \right) + 4\left( {s + p_{2} } \right),F\left( {3,4,1,1} \right) + e_{2} } \right\} = { \hbox{min} } \left\{ {57 + 28, \, \infty } \right\} = 85. \\ & j = 1,F\left( {1,0,0,0} \right) = e_{1} + e_{2} + e_{3} + e_{4} + e_{5} = 104, \\ & F\left( {1,1,1,1} \right) = { \hbox{min} }\left\{ {F\left( {2,0,0,0} \right) + s + p_{1} , F\left( {2, 1, 1, 1} \right) + e_{1} } \right\} = { \hbox{min} }\left\{ {89 + 5, \, 71 + 15} \right\} = 86, \\ & F\left( {1,2,1,1} \right) = { \hbox{min} } \left\{ {F\left( {2,1,1,1} \right) + 2\left( {s + p_{1} } \right), F\left( {2,2,1,1} \right) + e_{1} } \right\} = { \hbox{min} }\left\{ {71 + 10, \, 67 + 15} \right\} = 81, \\ & F\left( {1,3,1,1} \right) = { \hbox{min} } \left\{ {F\left( {2,2,1,1} \right) + 3\left( {s + p_{1} } \right),F\left( {2,3,1,1} \right) + e_{1} } \right\} = { \hbox{min} } \left\{ {67 + 15, \, 71 + 15} \right\} = 82, \\ & F(1,4,1,1) = \hbox{min} \{ F(2,3,1,1) + 4(s + p_{1} ),F(2,4,1,1) + e_{1} \} = \hbox{min} \{ 71 + 20,85 + 15\} = 91 \\ & F\left( {1,5,1,1} \right) = { \hbox{min} }\left\{ {F\left( {2,4,1,1} \right) + 5\left( {s + p_{1} } \right),F\left( {2,5,1,1} \right) + e_{1} } \right\} = { \hbox{min} }\left\{ {85 + 25, \infty } \right\} = 110. \\ \end{aligned} $$

Then, for the case h = 2, 3, 4, 5, we can similarly compute the function value. Finally, the optimal value is min {F(1, i, h, h)| 0 ≤ i ≤ n, 0 ≤ h ≤ i.} = F(1, 2, 1, 1) = 81. The corresponding optimal schedule can be found by backtracking. The set of accepted jobs is \( \overline{R} = \{ J_{1} ,J_{4} \} \) and each job is processed in a single batch such that there are two batches: {J 1} and {J 4}; The set of rejected jobs is R = {J 2, J 3, J 5}.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zou, J., Miao, C. The single machine serial batch scheduling problems with rejection. Oper Res Int J 16, 211–221 (2016). https://doi.org/10.1007/s12351-015-0193-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-015-0193-x

Keywords

Search

Navigation