Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scheduling
Published in: Journal of Scheduling 4/2018

05-10-2017

Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time

Authors: Zhijun Xu, Dehua Xu

Published in: Journal of Scheduling | Issue 4/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider a single-machine tool change scheduling problem where tool change durations are workload-dependent. The processing times of all the jobs are the same. The objective is to determine the number of tool change activities, the start time and the completion time of each tool change activity jointly and schedule all the jobs to the machine such that the total completion time of the jobs is minimized. For the case where the tool change duration function is concave, we present a linear time optimal algorithm. For the case where the tool change duration function is convex, we convert it into a convex integer quadratic programming problem with fixed dimension and then propose two polynomial time algorithms for it. We also study some special cases for which optimal schedules can be obtained directly. For the case where the tool change duration function is linear, we present all the optimal schedules.
previous article Integrated production and outbound distribution scheduling problems with job release dates and deadlines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
Akturk, M. S., Ghosh, J. B., & Gunes, E. D. (2003). Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance. Naval Research Logistics, 50(1), 15–30.CrossRef
Akturk, M. S., Ghosh, J. B., & Gunes, E. D. (2004). Scheduling with tool changes to minimize total completion time: Basic results and SPT performance. European Journal of Operational Research, 157(3), 784–790.CrossRef
Akturk, M. S., Ghosh, J. B., & Kayan, R. K. (2007). Scheduling with tool changes to minimize total completion time under controllable machining conditions. Computers & Operations Research, 34(7), 2130–2146.CrossRef
Baptiste, P., & Schieber, B. (2003). A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. Journal of Scheduling, 6(4), 395–404.CrossRef
Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28(5), 205–212.CrossRef
Birks, M., & Fung, S. P. Y. (2013). Temperature aware online algorithms for scheduling equal length jobs. Theoretical Computer Science, 508, 54–65.CrossRef
Blazewicz, J., Ecker, K., Kis, T., Potts, C. N., Tanas, M., & Whitehead, J. (2010). Scheduling of coupled tasks with unit processing times. Journal of Scheduling, 13(5), 453–461.CrossRef
Brucker, P., & Shakhlevich, N. V. (2016). Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines. Journal of Scheduling, 19, 659–685.CrossRef
Chen, J. S. (2008). Optimization models for the tool change scheduling problem. Omega, 36(5), 888–894.CrossRef
Gerstl, E., & Mosheiov, G. (2013a). Due-window assignment problems with unit-time jobs. Applied Mathematics and Computation, 220, 487–495.CrossRef
Gerstl, E., & Mosheiov, G. (2013b). Due-window assignment with identical jobs on parallel uniform machines. European Journal of Operational Research, 229(1), 41–47.CrossRef
Gerstl, E., & Mosheiov, G. (2013c). An improved algorithm for due-window assignment on parallel identical machines with unit-time jobs. Information Processing Letters, 113(19), 754–759.CrossRef
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.CrossRef
Heinz, S. (2005). Complexity of integer quasiconvex polynomial optimization. Journal of Complexity, 21(4), 543–556.CrossRef
Hemmecke, R., Köppe, M., Lee, J., & Weismantel, R. (2010). Nonlinear integer programming. In 50 years of integer programming 1958–2008 (pp. 561–618). New York, NY: Springer.
Jackson, J. R. (1956). An extension of Johnson’s results on job IDT scheduling. Naval Research Logistics Quarterly, 3(3), 201–203.CrossRef
Janiak, A., Janiak, W., Kovalyov, M. Y., & Werner, F. (2012). Soft due window assignment and scheduling of unit-time jobs on parallel machines. 4OR, 10(4), 347–360.CrossRef
Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.CrossRef
Lenstra, H. W, Jr. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538–548.CrossRef
Li, C. L., Mosheiov, G., & Yovel, U. (2008). An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs. Computers & Operations Research, 35(11), 3612–3619.CrossRef
Li, W., Yuan, J., & Yang, S. (2014). Online scheduling of incompatible unit-length job families with lookahead. Theoretical Computer Science, 543, 120–125.CrossRef
Luo, T., Xu, Y., Luo, L., & He, C. (2014). Semi-online scheduling with two gos levels and unit processing time. Theoretical Computer Science, 521, 62–72.CrossRef
Luo, W., Cheng, T. E., & Ji, M. (2015). Single-machine scheduling with a variable maintenance activity. Computers & Industrial Engineering, 79, 168–174.CrossRef
Luo, W., & Ji, M. (2015). Scheduling a variable maintenance and linear deteriorating jobs on a single machine. Information Processing Letters, 115(1), 33–39.CrossRef
Mosheiov, G., & Shadmon, M. (2001). Minmax earliness-tardiness costs with unit processing time jobs. European Journal of Operational Research, 130(3), 638–652.CrossRef
Mosheiov, G., & Yovel, U. (2006). Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs. European Journal of Operational Research, 172(2), 528–544.CrossRef
Oron, D., Shabtay, D., & Steiner, G. (2015). Single machine scheduling with two competing agents and equal job processing times. European Journal of Operational Research, 244(1), 86–99.CrossRef
Pinedo, M. L. (2012). Scheduling: Theory, algorithms, and systems (4th ed.). New York, NY: Springer.CrossRef
Qi, X. (2007). A note on worst-case performance of heuristics for maintenance scheduling problems. Discrete Applied Mathematics, 155(3), 416–422.CrossRef
Qi, X., Chen, T., & Tu, T. (1999). Scheduling the maintenance on a single machine. Journal of the Operational Research Society, 50, 1071–1078.CrossRef
Quilliot, A., & Chrétienne, P. (2013). Homogeneously non-idling schedules of unit-time jobs on identical parallel machines. Discrete Applied Mathematics, 161(10), 1586–1597.CrossRef
Rodriguez, C. E. P., & de Souza, G. F. M. (2010). Reliability concepts applied to cutting tool change time. Reliability Engineering & System Safety, 95(8), 866–873.CrossRef
Sarin, S. C., & Prakash, D. (2004). Equal processing time bicriteria scheduling on parallel machines. Journal of Combinatorial Optimization, 8(3), 227–240.CrossRef
Shabtay, D., & Karhi, S. (2012a). An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times. Discrete Optimization, 9(4), 241–248.CrossRef
Shabtay, D., & Karhi, S. (2012b). Online scheduling of two job types on a set of multipurpose machines with unit processing times. Computers & Operations Research, 39(2), 405–412.CrossRef
Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1–2), 59–66.CrossRef
Tuong, N. H., & Soukhal, A. (2010). Due dates assignment and JIT scheduling with equal-size jobs. European Journal of Operational Research, 205(2), 280–289.CrossRef
Xu, D., Liu, M., Yin, Y., & Hao, J. (2013). Scheduling tool changes and special jobs on a single machine to minimize makespan. Omega-International Journal of Management Science, 41(2), 299–304.CrossRef
Xu, D., Wan, L., Liu, A., & Yang, D. L. (2015). Single machine total completion time scheduling problem with workload-dependent maintenance duration. Omega-International Journal of Management Science, 52, 101–106.CrossRef
Xu, D., Yin, Y., & Li, H. (2010). Scheduling jobs under increasing linear machine maintenance time. Journal of Scheduling, 13(4), 443–449.CrossRef
Xu, Z., & Xu, D. (2015). Single-machine scheduling with preemptive jobs and workload-dependent maintenance durations. Operational Research, 15(3), 423–436.CrossRef
Metadata
Title
Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time
Authors
Zhijun Xu
Dehua Xu
Publication date
05-10-2017
Publisher
Springer US
Published in
Journal of Scheduling / Issue 4/2018
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-017-0543-z

Other articles of this Issue 4/2018

Journal of Scheduling 4/2018 Go to the issue

OriginalPaper

Integrated production and outbound distribution scheduling problems with job release dates and deadlines

OriginalPaper

Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem

OriginalPaper

Two-stage hybrid flowshop scheduling with simultaneous processing machines

OriginalPaper

Online-bounded analysis