Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions

Chung-Lun Li* and Qingying Li

The Hong Kong Polytechnic University, Hong Kong, China

We consider the problem of scheduling a given set of n jobs with equal processing times onm parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines.

The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem inO(n2 +mnlogn) time.

We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.

Journal of the Operational Research Society advance online publication, 19 March 2014; doi:10.1057/jors.2014.22

Keywords: scheduling; parallel machines; equal processing time jobs; inclusive processing sets 1. Introduction

We consider the problem of scheduling a given set {J1, J2,…,

Jn} of n independent jobs on m parallel machines so as to minimize the makespan of the schedule. Let M¼ fM1; M2; ;Mmg denote the set of all machines. All jobs have the same processing time p> 0, and job preemption is not allowed. Associated with each job Jj is a release date rj⩾ 0 and a ‘grade’ aj. The start time of Jj cannot be earlier than its release date rj. In addition, Jj can be processed by any one of the machines Maj,Maj+1,…,Mm, but not by any of the machines

M1,M2,…,Maj− 1. In other words, the machines are linearly ordered and indexed in such a way thatMi+1 can process all the jobs that Mi can process, for i= 1, 2,…,m− 1. This type of parallel machine processing restriction is called ‘inclusive processing set restriction’ (also known as ‘grade of service eligibility constraints’). It represents a situation in which the machines have different levels of capability, and machine

Mi is capable of processing jobs of grade i or below.

Using the notation in Leung and Li (2008), this problem is denoted as PjMjðinclusiveÞ; rj; pj ¼ pjCmax; where Mj ¼ fMaj ; Maj + 1; ¼ ;Mmg denotes the ‘processing set’ of Jj, parameter pj denotes the processing time of job Jj, and Cmax denotes the maximum machine completion time (ie, the makespan of the schedule).

Parallel machine scheduling problems with inclusive processing set restrictions are of practical value, and processors with such restrictions can be found in many real-life situations. For example, in the service industry, service providers often classify their customers into different grades such as silver, gold, or platinum members. Each customer should then be served by a server with a ‘grade-of-service level’ no lower than the grade of the customer (Hwang et al, 2004). In cargo loading operations, multiple cranes with different weight capacity limits could be operating simultaneously, and each piece of cargo can only be handled by a crane with a weight capacity limit no less than the weight of the cargo (Ou et al, 2008). In general, companies often invest in their production and service facilities in such a way that processors with different levels of capability are operated in parallel to process jobs with different requirements.

Consider a coating process that applies a covering to the surface of product parts. The coating process involves m coating machines that have the same functionality but are of different capacities (ie, they can accommodate product parts of different physical sizes). Each coating cycle has a constant duration p. A group of parts to be coated together by a coating machine is referred to as a job. Thus, the processing time of each job is p. A job can be assigned to any coating machine that has a capacity no smaller than the physical size of the job. The release time of the job is the time where the job is available for processing, and is dependent on the materials requirement plan.

If we wish to complete the processing of a group of given jobs as early as possible, then the problem fits into the model

PjMjðinclusiveÞ; rj; pj ¼ pjCmax:

Scheduling problems with inclusive processing set restrictions have been studied by many researchers; see Leung and Li (2008) for a survey on scheduling with processing set restrictions in general and Lim (2010) for a survey on scheduling with inclusive processing set restrictions in particular. See also Lee et al (2013) for a recent review of online scheduling problems with processing set restrictions. When job preemption is not allowed and the processing times and release dates of jobs are different, the problem is NP-hard in the strong sense (Lawler et al, 1993). Li and Wang (2010) have developed a polynomial *Correspondence: Chung-Lun Li, Department of Logistics and Maritime

Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong

Kong, China

E-mail: chung-lun.li@polyu.edu.hk

Journal of the Operational Research Society (2014), 1–8 © 2014 Operational Research Society Ltd. All rights reserved. 0160-5682/14 www.palgrave-journals.com/jors/ time approximation scheme for this problem. When jobs have equal processing times, the problem becomes polynomial time solvable. Lee et al (2011) have developed a polynomial time algorithm for PjMj; rj ; pj ¼ pjCmax; which allows a general processing set restriction (ie,Mj can be any subset ofM). This algorithm has a running time of O(m3/2n5/2logn). As our problem is a special case of PjMj; rj; pj ¼ pjCmax; it can be solved by Lee et al’s (2011) algorithm. As mentioned above, our problem is an important special case with specific applications. Therefore, in this paper we would like to present a more efficient algorithm for our problem with a running time of

O(n2 +mnlogn).

Another work related to this research is presented by

Li (2006), who has developed an O(n2(m+ logn)logn) algorithm for PjMj; pj ¼ 1jCmax: In his model, the jobs do not have any release date and are available for processing at time 0. 2. The solution procedure and its complexity