SINGLE-MACHINE SCHEDULING OF THE INDIVISIBLE MULTI-OPERATION JOBS

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

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.


Keywords


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

Full Text:

PDF


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

Refbacks

  • There are currently no refbacks.




Copyright (c) 2019 Ferda Can Çetinkaya, Hale Akkocaoğlu Çatmakaş, Abdül Kadir Görür


ISSN 2224-7890 (on-line) ; ISSN 1012-277X (print)


Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


Disclaimer:

This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help