Parallel machine scheduling with earliness-tardiness penalties and space limits

Suk Jae Jeong, Kyung Sup Kim

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.

Original languageEnglish
Pages (from-to)793-802
Number of pages10
JournalInternational Journal of Advanced Manufacturing Technology
Issue number7-8
Publication statusPublished - 2008 Jun

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Mechanical Engineering
  • Computer Science Applications
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Parallel machine scheduling with earliness-tardiness penalties and space limits'. Together they form a unique fingerprint.

Cite this