Group scheduling with group-dependent multiple due windows assignment

Min Ji, Xin Zhang, Xiaoying Tang, Edwin Tai Chiu Cheng, Guiyi Wei, Yuanyuan Tan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

We consider single-machine group scheduling with group-dependent multiple due windows assignment. In the group technology environment, the jobs are divided into groups in advance according to their processing similarities, and all the jobs of the same group are processed consecutively in order to improve production efficiency. A sequence-independent machine set-up time precedes the processing of the first job of each group. Each group has group-dependent multiple due windows. The objective is to find the optimal job sequence, the set of jobs assigned to each due window sequence, the optimal group sequence, and the optimal due window assignment to minimise a total cost that comprises the earliness and tardiness penalties and the due window starting time and due window size costs. For the case where the number of jobs assigned to each due window in each group is given in advance, we show that the problem is solvable O(nlog n) in time, where n is the total number of jobs. For the case where the number of jobs assigned to each due window in each group is unknown, we give an O(nBlog n) time algorithm to solve the problem, where B = Max{hi-1} and hiis the number of due window of the ith group.
Original languageEnglish
Pages (from-to)1244-1256
Number of pages13
JournalInternational Journal of Production Research
Volume54
Issue number4
DOIs
Publication statusPublished - 16 Feb 2016

Keywords

  • earliness/tardiness
  • group technology
  • group-dependent multiple due windows
  • single-machine scheduling

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this