Machine scheduling with job class setup and delivery considerations

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


We study machine scheduling problems in which the jobs belong to different job classes and they need to be delivered to customers after processing. A setup time is required for a job if it is the first job to be processed on a machine or its processing on a machine follows a job that belongs to another class. Processed jobs are delivered in batches to their respective customers. The batch size is limited by the capacity of the delivery vehicles and each shipment incurs a transport cost and takes a fixed amount of time. The objective is to minimize the weighted sum of the last arrival time of jobs to customers and the delivery (transportation) cost. For the problem of processing jobs on a single machine and delivering them to multiple customers, we develop a dynamic programming algorithm to solve the problem optimally. For the problem of processing jobs on parallel machines and delivering them to a single customer, we propose a heuristic and analyze its performance bound.
Original languageEnglish
Pages (from-to)1123-1128
Number of pages6
JournalComputers and Operations Research
Issue number6
Publication statusPublished - 1 Jun 2010


  • Algorithms
  • Job class setup
  • Machine scheduling
  • Transportation

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Machine scheduling with job class setup and delivery considerations'. Together they form a unique fingerprint.

Cite this