SINGLE-MACHINE SCHEDULING OF THE INDIVISIBLE MULTI-OPERATION JOBS

Authors

  • Ferda Can Çetinkaya Çankaya University
  • Hale Akkocaoğlu Çatmakaş Çankaya University
  • Abdül Kadir Görür Çankaya University

DOI:

https://doi.org/10.7166/30-1-2017

Keywords:

single-machine scheduling, multi-operation jobs, indivisible jobs, customer order scheduling, makespan, total completion time

Abstract

This paper considers a single-machine scheduling problem of multi- operation jobs where each job consists of several operations processed contiguously, rather than being intermingled with the operations of different jobs. That is, the jobs are indivisible. A sequence-independent setup is required if the machine switches from one operation to another. However, no setup is necessary before the first operation of a job if this first operation is the same as the last operation of the immediately previous job. A job is complete when all of its operations have been processed. We investigate the problem for two cases. Makespan, which is the time needed to complete all jobs, is minimised in the first case; whereas the total completion time, which is the sum of the job completion times, is minimised in the second case. We show that the makespan problem is solvable in polynomial time. For the problem of minimising total completion time, we develop a mixed integer linear programming (MILP) model, which is capable of solving small and medium-sized problem instances optimally, and obtain a very small gap between the solution found and the best possible solution for the unsolved large-sized problem instances.

Downloads

Download data is not yet available.

Author Biographies

Ferda Can Çetinkaya, Çankaya University

Ferda Can Çetinkaya is an Associate Professor of Industrial Engineering and the Chairperson of Industrial Engineering Department at the Çankaya University, Turkey. He obtained his BS, MS and PhD degrees in Industrial Engineering from the Middle East Technical University, Ankara, Turkey. His primary research areas are machine scheduling, production systems modelling and optimisation, logistics systems, project scheduling and control, and technology management.

Hale Akkocaoğlu Çatmakaş, Çankaya University

Hale Akkocaoğlu Çatmakaş received his BS and MS degrees in Industrial Engineering from the Çankaya University. Currently, she is is a PhD candidate in Industrial Engineering at the Middle East Technical University, and working as a lecturer in Industrial Engineering Department at the Çankaya University as a lecturer. Her research areas are scheduling, production planning and humanitarian logistics.

Abdül Kadir Görür, Çankaya University

Abdül Kadir Görür is an Assistant Professor of Computer Engineering at the Çankaya University. He obtained his BS, MS and PhD degrees in Computer Engineering from the Eastern Mediterranean University, North Cyprus. His research interests include the information retrieval, text categorization, search engines, and mathematical modelling.

Downloads

Published

2019-05-29

How to Cite

Çetinkaya, F. C., Çatmakaş, H. A., & Görür, A. K. (2019). SINGLE-MACHINE SCHEDULING OF THE INDIVISIBLE MULTI-OPERATION JOBS. The South African Journal of Industrial Engineering, 30(1), 78–93. https://doi.org/10.7166/30-1-2017

Issue

Vol. 30 No. 1 (2019)

Section

General Articles

License

Authors who publish in the Journal agree to the following terms:
  1. Authors retain copyright and grant the Journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this Journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the Journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this Journal.