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

A note: maximizing the weighted number of Just-in-Time jobs for a given job sequence

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

We study a single machine scheduling problem to maximize the weighted number of Just-in-Time jobs, i.e., jobs which are completed exactly at their due-dates. We focus on the case that the job sequence is given. A pseudo-polynomial solution algorithm has been published for this problem, and we introduce here an efficient polynomial time dynamic programming algorithm. The new algorithm is tested numerically, and the results are compared to those obtained by the old algorithm. While the running times required by both algorithms for solving large instances are extremely small, it appears that the new algorithm performs better in two aspects: (1) The resulting running time is independent of the actual density of the due-dates, (2) The required memory is significantly reduced. An extension to a two-machine flowshop is provided, and this case is shown to remain polynomially solvable.

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Chen, R. X., Li, S. S., & Li, W. J. (2019). Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs. Engineering Optimization, 51(2), 217–230.

    Article  Google Scholar 

  • Choi, B. C., & Yoon, S. H. (2007). Maximizing the weighted number of just-in-time jobs in flow shop scheduling. Journal of Scheduling, 10(4), 237–243.

    Article  Google Scholar 

  • Elalouf, A., Levner, E., & Tang, H. (2013). An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. Journal of Scheduling, 16(4), 429–435.

    Article  Google Scholar 

  • Fry, T., Armstrong, R. D., & Rosen, L. D. (1990). Single machine scheduling to minimize mean absolute lateness: A heuristic solution. Computers & Operations Research, 17, 105–112.

    Article  Google Scholar 

  • Fry, T. D., Armstrong, R. D., & Blackstone, J. H. (1987). Minimizing weighted absolute deviation in single machine scheduling. IIE Transactions, 19, 445–450.

    Article  Google Scholar 

  • Gerstl, E., Mor, B., & Mosheiov, G. (2015). A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop. Information Processing Letters, 115, 159–162.

    Article  Google Scholar 

  • Gerstl, E., & Mosheiov, G. (2020). Single machine scheduling to maximize the number of on-time jobs with generalized due-dates. Journal of Scheduling, 23(3), 289–299.

    Article  Google Scholar 

  • Gilenson, M., & Shabtay, D. (2019). Multi-scenario scheduling to maximise the weighted number of just-in-time jobs. Journal of the Operational Research Society, 72, 1–18.

    Google Scholar 

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

    Article  Google Scholar 

  • Hiraishi, K., Levner, E., & Vlach, M. (2002). Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs. Computers & Operations Research, 29(7), 841–848.

    Article  Google Scholar 

  • Jolai, F., Amalnick, M. S., Alinaghian, M., Shakhsi-Niaei, M., & Omrani, H. (2011). A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines. Journal of Intelligent Manufacturing, 22(2), 247–261.

    Article  Google Scholar 

  • Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85–103). Boston, MA: Springer.

  • Lann, A., & Mosheiov, G. (1996). Single machine scheduling to minimize the number of early/tardy jobs. Computers and Operations Research, 23, 769–781.

    Article  Google Scholar 

  • Liaw, C. F., Cheng, C. Y., & Chen, M. (2002). The total completion time open shop scheduling problem with a given sequence of jobs on one machine. Computers & Operations Research, 29, 1251–1266.

    Article  Google Scholar 

  • Mosheiov, G., & Shabtay, D. (2013). Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Journal of Scheduling, 16, 519–527.

    Article  Google Scholar 

  • Shabtay, D. (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216, 521–532.

    Article  Google Scholar 

  • Shabtay, D., & Bensoussan, Y. (2012). Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems. Journal of Scheduling, 15(1), 39–47.

    Article  Google Scholar 

  • 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(1), 67–74.

    Article  Google Scholar 

  • Shafransky, Y. M., & Strusevich, V. A. (1998). The open shop scheduling problem with a given sequence of jobs on one machine. Naval Research Logistics, 45, 705–731.

    Article  Google Scholar 

  • Sung, S. C., & Vlach, M. (2005). Maximizing weighted number of just-in-time jobs on unrelated parallel machines. Journal of Scheduling, 8(5), 453–460.

    Article  Google Scholar 

  • Yin, Y., Cheng, S.-R., Cheng, T. C. E., Wang, D.-W., & Wu, C.-C. (2016). Just-in-time scheduling with two competing agents on unrelated parallel machines. Omega, 63, 41–47.

    Article  Google Scholar 

  • Yin, Y., Cheng, T. C. E., Wang, D. J., & Wu, C. C. (2017). Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs. Journal of Scheduling, 20(4), 313–335.

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported by the Israel Science Foundation (Grant No.2505/19), by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – (Project Number 452470135) and by the Recanati Fund of The School of Business Administration, The Hebrew University of Jerusalem, Israel.

Author information

Authors and Affiliations

  1. School of Business Administration, The Hebrew University, Jerusalem, Israel

    Enrique Gerstl & Gur Mosheiov

  2. Jerusalem College of Technology, Lev Academic Center, Jerusalem, Israel

    Gur Mosheiov

Authors
  1. Enrique Gerstl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gur Mosheiov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gur Mosheiov.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Algorithm DP2 introduced by Lann and Mosheiov (1996)

Appendix: Algorithm DP2 introduced by Lann and Mosheiov (1996)

Jobs are numbered according to the given sequence.

State variables:

\(j\): index of the current job,

\(t\): the completion time of the job \(j-1\).

The return function:

\(f\left(t,j\right):\) minimum cost of scheduling jobs \(j,...,n\), where the starting time of job \(j\) does not precede \(t\). Thus, the recursion is given by:

$$ f\left( {t,j} \right) = \left\{ {\begin{array}{*{20}c} {\min \left\{ {w_{j}^{E} + f\left( {t + p_{j} , j + 1} \right), f\left( {d_{j} ,j + 1} \right)} \right\}} & {{\text{if}}\quad t + p_{j} \le d_{j} } \\ {w_{j}^{T} + f\left( {t + p_{j} , j + 1} \right)} & {{\text{otherwise}}} \\ \end{array} } \right.. $$

[Note that the first line reflects the case that the current job can be scheduled on time, so it is either scheduled as early as possible, i.e., at time \(t\), or scheduled to be completed at the due-date. The second line reflects the case that the job must be tardy, and then it is scheduled as early as possible.]

The boundary conditions are: \(f(t, n + 1) = 0\) for all values of \(t\).

The optimal cost is given by \(f(0, 1)\).

Running time: Let \({d}_{\mathrm{max}}=\mathrm{max}\{{d}_{j}, j=1,\dots ,n\}\), and recall that \(P={\sum }_{j=1}^{n}{p}_{j}.\) Thus, an upper bound on the value of \(t\) is \(\mathrm{max}\{{d}_{\mathrm{max}}, P\}\). \(j\) is bounded by \(n\). The computation of \(f(t,j)\) requires a constant time. It follows that the running time of DP2 is \(O(n \mathrm{max}\{{d}_{\mathrm{max}}, P\}\).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gerstl, E., Mosheiov, G. A note: maximizing the weighted number of Just-in-Time jobs for a given job sequence. J Sched 26, 403–409 (2023). https://doi.org/10.1007/s10951-022-00772-4

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-022-00772-4

Keywords

Search

Navigation