\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time

  • * Corresponding author: Jinjiang Yuan

    * Corresponding author: Jinjiang Yuan
The authors are supported by NSFC (11671368), NSFC (11571321), and NSFC (11771406)
Abstract Full Text(HTML) Figure(2) / Table(4) Related Papers Cited by
  • This paper investigates the scheduling of family jobs with release dates on an unbounded parallel-batch machine. The involved objective functions are makespan and maximum flow time. It was reported in the literature that the single-criterion problem for minimizing makespan is strongly NP-hard when the number of families is arbitrary, and is polynomially solvable when the number of families is fixed. We first show in this paper that the single-criterion problem for minimizing maximum flow time is also strongly NP-hard when the number of families is arbitrary. We further show that the Pareto optimization problem (also called bicriteria problem) for minimizing makespan and maximum flow time is polynomially solvable when the number of families is fixed, by enumerating all Pareto optimal points in polynomial time. This implies that the single-criterion problem for minimizing maximum flow time is also polynomially solvable when the number of families is fixed.

    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The structure of the scheduling problem

    Figure 2.  An intuitive interpretation of the proposed algorithm

    Table 1.  The definitions of the abbreviations/notations

    Abbreviation/Notation Definition
    ERD earliest release date first (rule)
    PoP Pareto optimal point
    PoS Pareto optimal schedule
    ERD-family scheule a schedule of family jobs defined in the first paragraph in section 3.1
    ${\mathcal F}_f$ the $f$-th job family
    $f$-job a job which belongs to family ${\mathcal F}_f$
    $f$-batch a p-bath which only includes $f$-jobs
    $J_{f, j}$ the $j$-th job in family ${\mathcal F}_f$
    $J_{j}$ a general job
    $p_{j}~(p_{f, j})$/$r_{j}~(r_{f, j})$ the processing time/the release dates of job $J_{j}~(J_{f, j})$
    $n_f$ the number of jobs in family ${\mathcal F}_f$
    $(b<n)/(b\geq n)$ the bounded/unbounded capacity of a p-batch
    $p(B)$ the processing time of batch $B$
    $\pi/\sigma$ a feasible schedule
    $C_{j}(\pi)(C_{f, j}(\pi))$ the completion time of job $J_{j}$ ($J_{f, j}$) in $\pi$
    $S_{j}(\pi)(S_{f, j}(\pi))$ the starting time of job $J_{j}$ ($J_{f, j}$) in $\pi$
    $C_{B}(\pi)$ the completion time of batch $B$ in $\pi$
    $S_{B}(\pi)$ the starting time of batch $B$ in $\pi$
    $F_{j}(\pi)(F_{f, j}(\pi))$ the flow time of job $J_{j}$ ($J_{f, j}$) in $\pi$ which is $F_{j}(\pi)=C_{j}(\pi)-r_{j}(\pi)$
    $C_{\max}(\pi)$ the maximum completion time of all jobs in $\pi$
    $F_{\max}(\pi)$ the maximum flow time of all jobs in $\pi$
    ${\mathcal F}_f^{(i)}$ the set composed by the first $i$ jobs of family ${\mathcal F}_f$, i.e., $\{J_{f, 0}, J_{f, 1}, \cdots, J_{f, i}\}$
    $(i_1, \cdots, i_K)$ the instance composed by the job set ${\mathcal F}_1^{(i_1)} \cup \cdots \cup {\mathcal F}_K^{(i_K)}$
    $P(i_1, \cdots, i_K)$ the problem $1|\beta |^\#(C_{\max}, F_{\max})$ restricted on the instance $(i_1, \cdots, i_K)$
    $P_{Y}(i_1, \cdots, i_K)$ the problem $1|\beta |C_{\max}: F_{\max}\leq Y$ restricted on the instance $(i_1, \cdots, i_K)$
    $P_{Y}^{(f)}(i_1, \cdots, i_K)$ a restricted version of $P_{Y}(i_1, \cdots, i_K)$ with $i_f \geq 1$ for which it is required that feasible schedules end with an $f$-batch
    $C_Y^{(f)}(i_1, \cdots, i_K)$ the optimal makespan of problem $P_{Y}^{(f)}(i_1, \cdots, i_K)$
    $C_Y^{(f, k_f)}(i_1, \cdots, i_K)$ defined in equation (3)
    $D_Y^{(f)}(i_1, \cdots, i_K)$ defined in equation (4)
    ${\mathcal X}_{Y}(i_1, \cdots, i_K)$ defined in equation (5), the set of family indices attaining the minimum in equation (1)
    $\Psi^{(f)}_{Y}(i_1, \cdots, i_K)$ defined in equation (6), the set of the $f$-job indices attaining the minimum in equation (2)
    $C_Y(i_1, \cdots, i_K)$ the optimal makespan of problem $P_{Y}(i_1, \cdots, i_K)$
    Algorithm DP($Y$) the proposed dynamic programming algorithm for problem $1|\beta |C_{\max}: F_{\max}\leq Y$
    Algorithm Family-CF the proposed algorithm for problem $1|\beta |^\#(C_{\max}, F_{\max})$
     | Show Table
    DownLoad: CSV

    Table 2.  The jobs in family ${\mathcal F}_1$

    ${\mathcal F}_1$ $J_{1, 1}$ $J_{1, 2}$ $J_{1, 3}$ $J_{1, 4}$ $J_{1, 5}$ $J_{1, 6}$ $J_{1, 7}$ $J_{1, 8}$ $J_{1, 9}$ $J_{1, 10}$
    $r_{1, i}$ 0 2 3 4 6 7 9 11 14 17
    $p_{1, i}$ 2 2 4 5 7 12 3 6 1 3
     | Show Table
    DownLoad: CSV

    Table 3.  The jobs in family ${\mathcal F}_2$

    ${\mathcal F}_1$ $J_{1, 1}$ $J_{1, 2}$ $J_{1, 3}$ $J_{1, 4}$ $J_{1, 5}$ $J_{1, 6}$ $J_{1, 7}$ $J_{1, 8}$ $J_{1, 9}$ $J_{1, 10}$
    $r_{1, i}$ 1 2 4 6 8 10 11 14 16 19
    $p_{1, i}$ 2 1 1 4 3 8 10 2 11 9
     | Show Table
    DownLoad: CSV

    Table 4.  The PoPs of the instances

    jobs PoPs jobs PoPs jobs PoPs jobs PoPs jobs PoPs
    ${\mathcal J}(1, 1)$ $(4, 3)$ ${\mathcal J}(1, 2)$ $(4, 3)$ ${\mathcal J}(2, 1)$ $(6, 4)$ ${\mathcal J}(2, 2)$ $(6, 4)$ ${\mathcal J}(1, 3)$ $(5, 3)$
    $(5, 5)$
    ${\mathcal J}(2, 3)$ $(5, 4)$ ${\mathcal J}(3, 1)$ $(8, 6)$ ${\mathcal J}(3, 2)$ $(8, 5)$ ${\mathcal J}(3, 3)$ $(9, 5)$ ${\mathcal J}(1, 4)$ $(2, 2)$
    $(7, 7)$ $(7, 7)$ $(8, 7)$
    ${\mathcal J}(2, 4)$ $(4, 2)$ ${\mathcal J}(3, 4)$ $(7, 5)$ ${\mathcal J}(4, 1)$ $(3, 2)$ ${\mathcal J}(4, 2)$ $(4, 2)$ ${\mathcal J}(4, 3)$ $(5, 2)$
    ${\mathcal J}(4, 4)$ $(10, 4)$ ${\mathcal J}(1, 5)$ $(2, 2)$ ${\mathcal J}(2, 5)$ $(4, 2)$ ${\mathcal J}(3, 5)$ $(7, 5)$ ${\mathcal J}(4, 5)$ $(13, 5)$
    $(9, 6)$ $(9, 6)$
    ${\mathcal J}(5, 1)$ $(3, 2)$ ${\mathcal J}(5, 2)$ $(4, 2)$ ${\mathcal J}(5, 3)$ $(5, 2)$ ${\mathcal J}(5, 4)$ $(10, 4)$ ${\mathcal J}(5, 5)$ $(13, 5)$
    $(12, 6)$
    ${\mathcal J}(1, 6)$ $(2, 2)$ ${\mathcal J}(2, 6)$ $(4, 2)$ ${\mathcal J}(3, 6)$ $(7, 5)$ ${\mathcal J}(4, 6)$ $(9, 6)$ ${\mathcal J}(5, 6)$ $(13, 10)$
    ${\mathcal J}(6, 1)$ $(3, 2)$ ${\mathcal J}(6, 2)$ $(4, 2)$ ${\mathcal J}(6, 3)$ $(5, 2)$ ${\mathcal J}(6, 4)$ $(10, 4)$ ${\mathcal J}(6, 5)$ $(13, 5)$
    $(12, 6)$
    ${\mathcal J}(6, 6)$ $(18, 10)$ ${\mathcal J}(1, 7)$ $(2, 2)$ ${\mathcal J}(2, 7)$ $(4, 2)$ ${\mathcal J}(3, 7)$ $(7, 5)$ ${\mathcal J}(4, 7)$ $(9, 6)$
    ${\mathcal J}(5, 7)$ $(13, 10)$ ${\mathcal J}(6, 7)$ $(22, 12)$ ${\mathcal J}(7, 1)$ $(3, 2)$ ${\mathcal J}(7, 2)$ $(4, 2)$ ${\mathcal J}(7, 3)$ $(5, 2)$
    $(21, 13)$
    $(19, 15)$
    ${\mathcal J}(7, 4)$ $(10, 4)$ ${\mathcal J}(7, 5)$ $(13, 5)$ ${\mathcal J}(7, 6)$ $(18, 10)$ ${\mathcal J}(7, 7)$ $(22, 12)$ ${\mathcal J}(1, 8)$ $(2, 2)$
    $(12, 6)$ $(21, 13)$
    ${\mathcal J}(2, 8)$ $(4, 2)$ ${\mathcal J}(3, 8)$ $(7, 5)$ ${\mathcal J}(4, 8)$ $(9, 6)$ ${\mathcal J}(5, 8)$ $(13, 10)$ ${\mathcal J}(6, 8)$ $(24, 12)$
    $(23, 13)$
    $(19, 15)$
    ${\mathcal J}(7, 8)$ $(24, 12)$ ${\mathcal J}(8, 1)$ $(3, 2)$ ${\mathcal J}(8, 2)$ $(4, 2)$ ${\mathcal J}(8, 3)$ $(5, 2)$ ${\mathcal J}(8, 4)$ $(10, 4)$
    $(23, 13)$
    $(21, 15)$
    ${\mathcal J}(8, 5)$ $(13, 5)$ ${\mathcal J}(8, 6)$ $(18, 10)$ ${\mathcal J}(8, 7)$ $(22, 12)$ ${\mathcal J}(8, 8)$ $(24, 12)$ ${\mathcal J}(1, 9)$ $(2, 2)$
    $(12, 6)$ $(21, 13)$ $(23, 13)$
    ${\mathcal J}(2, 9)$ $(4, 2)$ ${\mathcal J}(3, 9)$ $(7, 5)$ ${\mathcal J}(4, 9)$ $(9, 6)$ ${\mathcal J}(5, 9)$ $(13, 10)$ ${\mathcal J}(6, 9)$ $(19, 15)$
    ${\mathcal J}(7, 9)$ $(21, 15)$ ${\mathcal J}(8, 9)$ $(25, 16)$ ${\mathcal J}(9, 1)$ $(3, 2)$ ${\mathcal J}(9, 2)$ $(4, 2)$ ${\mathcal J}(9, 3)$ $(5, 2)$
    $(23, 17)$
    ${\mathcal J}(9, 4)$ $(10, 4)$ ${\mathcal J}(9, 5)$ $(13, 5)$ ${\mathcal J}(9, 6)$ $(18, 10)$ ${\mathcal J}(9, 7)$ $(22, 12)$ ${\mathcal J}(9, 8)$ $(24, 12)$
    $(12, 6)$ $(21, 13)$ $(23, 13)$
    ${\mathcal J}(9, 9)$ $(25, 16)$ ${\mathcal J}(1, 10)$ $(2, 2)$ ${\mathcal J}(2, 10)$ $(4, 2)$ ${\mathcal J}(3, 10)$ $(7, 5)$ ${\mathcal J}(4, 10)$ $(9, 6)$
    $(24, 17)$
    ${\mathcal J}(5, 10)$ $(13, 10)$ ${\mathcal J}(6, 10)$ $(19, 15)$ ${\mathcal J}(7, 10)$ $(21, 15)$ ${\mathcal J}(8, 10)$ $(25, 16)$ ${\mathcal J}(9, 10)$ $(25, 16)$
    $(23, 17)$ $(24, 17)$
    ${\mathcal J}(10, 1)$ $(3, 2)$ ${\mathcal J}(10, 2)$ $(4, 2)$ ${\mathcal J}(10, 3)$ $(5, 2)$ ${\mathcal J}(10, 4)$ $(13, 5)$ ${\mathcal J}(10, 5)$ $(18, 10)$
    $(12, 6)$
    ${\mathcal J}(10, 1)$ $(3, 2)$ ${\mathcal J}(10, 2)$ $(4, 2)$ ${\mathcal J}(10, 3)$ $(5, 2)$ ${\mathcal J}(10, 4)$ $(10, 4)$ ${\mathcal J}(10, 5)$ $(13, 5)$
    $(12, 6)$
    ${\mathcal J}(10, 6)$ $(18, 10)$ ${\mathcal J}(10, 7)$ $(22, 12)$ ${\mathcal J}(10, 8)$ $(24, 12)$ ${\mathcal J}(10, 9)$ $(25, 16)$ ${\mathcal J}(10, 10)$ $(25, 16)$
    $(21, 13)$ $(23, 13)$
     | Show Table
    DownLoad: CSV
  •   A. Allahverdi , C. T. Ng , T. C. E. Cheng  and  M. Y. Kovalyov , A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187 (2008) , 985-1032.  doi: 10.1016/j.ejor.2006.06.060.
      J. Bai , Z. R. Li  and  X. Huang , Single-machine group scheduling with general deterioration and learning effects, Applied Mathematical Modelling, 36 (2012) , 1267-1274.  doi: 10.1016/j.apm.2011.07.068.
      P. Brucker , A. Gladky , H. Hoogeveen , M. Y. Kovalyov , C. N. Potts  and  T. Tautenhahn , Scheduling a batching machine, Journal of Scheduling, 1 (1998) , 31-54.  doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R.
      K. Chakhlevitch , C. A. Glass  and  H. Kellerer , Batch machine production with perishability time windows and limited batch size, European Journal of Operational Research, 210 (2011) , 39-47.  doi: 10.1016/j.ejor.2010.10.033.
      T. C. E. Cheng , Z. H. Liu  and  W. C. Yu , Scheduling jobs with release dates and deadlines on a batch processing machine, IIE Transactions, 33 (2001) , 685-690. 
      Y. Gao  and  J. J. Yuan , A note on Pareto minimizing total completion time and maximum cost, Operational Research Letter, 43 (2015) , 80-82.  doi: 10.1016/j.orl.2014.12.001.
      Z. C. Geng  and  J. J. Yuan , Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness, Theoretical Computer Science, 570 (2015) , 22-29.  doi: 10.1016/j.tcs.2014.12.020.
      Z. C. Geng  and  J. J. Yuan , A note on unbounded parallel-batch scheduling, Information Processing Letters, 115 (2015) , 969-974.  doi: 10.1016/j.ipl.2015.07.002.
      C. He , Y. X. Lin  and  J. J. Yuan , Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan, Theoretical Computer Science, 381 (2007) , 234-240.  doi: 10.1016/j.tcs.2007.04.034.
      H. Hoogeveen , Multicriteria scheduling, European Journal of Operational Research, 167 (2005) , 592-623.  doi: 10.1016/j.ejor.2004.07.011.
      J. A. Hoogeveen , Single-machine scheduling to minimize a function of two or three maximum cost criteria, Journal of Algorithms, 21 (1996) , 415-433.  doi: 10.1006/jagm.1996.0051.
      J. A. Hoogeveen  and  S. L. van de Velde , Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Operations Research Letters, 17 (1995) , 205-208.  doi: 10.1016/0167-6377(95)00023-D.
      J. A. Hoogeveen  and  S. L. van de Velde , Scheduling with target start times, European Journal of Operational Research, 129 (2001) , 87-94.  doi: 10.1016/S0377-2217(99)00426-9.
      Y. Ikura  and  M. Gimple , Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters, 5 (1986) , 61-65.  doi: 10.1016/0167-6377(86)90104-5.
      F. Jolai , Minimizing number of tardy jobs on a batch processing machine with incompatible job families, European Journal of Operational Research, 162 (2005) , 184-190.  doi: 10.1016/j.ejor.2003.10.011.
      C. Y. Lee , R. Uzsoy  and  L. A. Martin-Vega , Efficient algorithms for scheduling semi-conductor burn-in operations, Operations Research, 40 (1992) , 764-775.  doi: 10.1287/opre.40.4.764.
      S. S. Li  and  R. X. Chen , Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs, Computers and Industrial Engineering, 73 (2014) , 5-10.  doi: 10.1016/j.cie.2014.04.007.
      S. S. Li , C. T. Ng , T. C. E. Cheng  and  J. J. Yuan , Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan, European Journal of Operational Research, 210 (2011) , 482-488.  doi: 10.1016/j.ejor.2010.11.021.
      S. S. Li  and  J. J. Yuan , Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan, Journal of Combinatorial Optimization, 19 (2010) , 84-93.  doi: 10.1007/s10878-008-9163-z.
      Z. H. Liu  and  W. C. Yu , Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics, 105 (2000) , 129-136.  doi: 10.1016/S0166-218X(00)00181-5.
      L. L. Liu  and  F. Zhang , Minimizing the number of tardy jobs on a batch processing machine with incompatible job families, ISECS International Colloquium on Computing, Communication, Control, and Management, 3 (2008) , 277-280.  doi: 10.1109/CCCM.2008.107.
      Z. H. Liu , J. J. Yuan  and  T. C. E. Cheng , On scheduling an unbounded batch machine, Operations Research Letters, 31 (2003) , 42-48.  doi: 10.1016/S0167-6377(02)00186-4.
      S. Malve  and  R. Uzsoy , A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families, Computers and Operations Research, 34 (2007) , 3016-3028.  doi: 10.1016/j.cor.2005.11.011.
      C. X. Miao , Y. Z. Zhang  and  Z. G. Cao , Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs, Information Processing Letters, 111 (2011) , 798-803.  doi: 10.1016/j.ipl.2011.05.018.
      Q. Q. Nong , C. T. Ng  and  T. C. E. Cheng , The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan, Operations Research Letters, 36 (2008) , 61-66.  doi: 10.1016/j.orl.2007.01.007.
      E. S. Pan , G. N. Wang , L. F. Xi , L. Chen  and  X. L. Han , Single-machine group scheduling problem considering learning, forgetting effects and preventive maintenance, International Journal of Production Research, 52 (2014) , 5690-5704.  doi: 10.1080/00207543.2014.904967.
      J. Pei , X. B. Liu , P. M. Pardalos , A. Migdalas  and  S. L. Yang , Serial-batching scheduling with time-dependent Setup time and effects of deterioration and learning on a single-machine, Journal of Global Optimization, 67 (2017) , 251-262.  doi: 10.1007/s10898-015-0320-5.
      J. Pei , B. Y. Cheng , X. B. Liu , P. M. Pardalos  and  M. Kong , Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time, Annals of Operations Research, (2017) , 1-25.  doi: 10.1007/s10479-017-2481-8.
      J. Pei , X. B. Liu , P. M. Pardalos , W. J. Fan  and  S. L. Yang , Single machine serial-batching scheduling with independent setup time and deteriorating job processing times, Optimization Letters, 9 (2015) , 91-104.  doi: 10.1007/s11590-014-0740-z.
      J. Pei , X. B. Liu , P. M. Pardalos , W. J. Fan  and  S. L. Yang , Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times, Annals of Operations Research, 249 (2017) , 175-195.  doi: 10.1007/s10479-015-1824-6.
      J. Pei , P. M. Pardalos , X. B. Liu , W. J. Fan  and  S. L. Yang , Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan, European Journal of Operational Research, 244 (2015) , 13-25.  doi: 10.1016/j.ejor.2014.11.034.
      C. N. Potts  and  M. Y. Kovalyov , Scheduling with batching: a review, European Journal of Operational Research, 120 (2000) , 228-249.  doi: 10.1016/S0377-2217(99)00153-8.
      X. L. Qi , S. G. Zhou  and  J. J. Yuan , Single machine parallel-batch scheduling with dete-riorating jobs, Theoretical Computer Science, 410 (2009) , 830-836.  doi: 10.1016/j.tcs.2008.11.009.
      V. T'kindt and  J. C. BillautMulticriteria Scheduling: Theory, Models and Algorithms, 2$^{nd}$ edition, Springer, Berlin, 2006.  doi: 10.1007/978-3-662-04986-0.
      H. Xuan  and  L. X. Tang , Scheduling a hybrid flowshop with batch production at the last stage, Computers and Operations Research, 34 (2007) , 2718-2733.  doi: 10.1016/j.cor.2005.10.014.
      J. J. Yuan , Z. H. Liu , C. T. Ng  and  T. C. E. Cheng , The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan, Theoretical Computer Science, 320 (2004) , 199-212.  doi: 10.1016/j.tcs.2004.01.038.
  • 加载中

Figures(2)

Tables(4)

SHARE

Article Metrics

HTML views(2224) PDF downloads(328) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return