Exponential neighborhood search for a parallel machine scheduling problem

https://doi.org/10.1016/j.cor.2006.10.008Get rights and content

Abstract

We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results.

Introduction

During the last years, just-in-time production has received a special interest. This concept reflects the aim to produce as close to the due date as possible in order to avoid storage costs when the production is early and additional costs resulting from a tardy delivery. The scheduling problem we study in this article stems from this just-in-time philosophy.

The problem we are interested in is about n jobs, J={1,2,,n}, that are to be executed on m identical parallel machines. Each machine Mj (j=1,,m) is available from time 0 and can only execute one job at the time. Each job i is also available from time 0 and has an execution time pi. The execution of a job is not preemptive: once the job starts it cannot be interrupted. We consider for this research the hypothesis of a common due date d=di (iJ), at which ideally all the jobs must end. From a practical point of view, a common due date appears when a set of jobs must be produced simultaneously to be assembled in a later production level or when a client orders various goods that are to be delivered at the same moment.

The aim is to find a schedule S that specifies the completion time Ci of each job. A job is early when it completes before the common due date. Given S, the earliness of a job i is defined as Ei=max{0,(d-Ci)}. Similarly, when a job ends after the due date then its tardiness is Ti=max{0,(Ci-d)}. Jobs whose completion time is d are said on time. Each job i has an earliness penalty αi and a tardiness one βi. Then, the total cost of a schedule S is f(S)=iJ(αiEi+βiTi).

The common due date is said to be large when iJpid. This large due date (dl) allows to ignore the constraint that makes the schedule to start at or after time 0 on every machine. In an intuitive way, if the optimal cost cannot decrease when the common due date increases, then the due date is unrestricted or large. Otherwise, the due date is called restrictive (dr). In this case, the due date is early enough to act as a constraint on the scheduling decision. For a more explicit definition of a restrictive due date we refer the reader to the article of Lauff and Werner [1]. The scheduling problem we investigate in this article has a restrictive common due date.

In the standard classification scheme of Graham et al. [2] the problem we study can be written as P|di=dr|i(αiEi+βiTi) (where P is for the identical parallel machine environment and di=dr means that all the jobs have the same restrictive due date). Several common due date scheduling surveys can be pointed out: Baker and Scudder [3], Gordon et al. [4] and Lauff and Werner [5].

The parallel machine problem without earliness or tardiness penalties and a large common due date is investigated by Hall [6] and Sundaraghavan and Ahmed [7]. They generalize Kanet's algorithm [8]. Emmons [9] proposes a O(nlogn) algorithm for Q|di=dl|i(Ei+Ti) and Q|di=dl|i(αEi+βTi), where Q means the parallel machines are uniform (different dependent speeds). He models the problem with a transportation formulation. Kubiak et al. [10] present a O(n3) algorithm for R|di=dl|i(Ei+Ti), where R denotes an unrelated parallel machine environment (the machines have different independent speeds).

Sun and Wang [11] consider the identical parallel machine problem with a large due date P|di=dl|iwi(Ci-d), where the weight wi of each job is proportional to its processing time. They show that even for m=2 the problem is NP-hard in the ordinary sense. They formulate a dynamic programming algorithm and consider two list scheduling heuristics. Chen and Powell [12] propose a column generation algorithm for the identical parallel machine problem with large common due date P|di=dl|i(αiEi+βiTi) and they optimally solve instances with up to 60 jobs with a branch-and-bound algorithm.

For the single machine problem with a large common due date, 1|di=dl|i(αiEi+βiTi), Lee and Kim [13] propose a parallel genetic algorithm and Van den Akker et al. [14] use a combination of column generation and Lagrangian relaxation to solve instances with up to 125 jobs.

Some earliness-tardiness problems can be solved in an exact way by pseudo-polynomial algorithms. To the best of our knowledge, this kind of algorithm has not been presented for the single machine version of the problem we study, 1|di=dr|i(αiEi+βiTi). In fact, some authors have conjectured that this problem is NP-hard in the strong sense [15], [16]. The parallel machine problem P|di=dr|i(αiEi+βiTi), inherits the characteristic of been NP-hard in the strong sense from the parallel machine problem PiwiCi [17, p. 152].

The manner we choose to tackle the problem P|di=dr|i(αiEi+βiTi) is by a neighborhood search algorithm (also known as local search). From an initial solution, this kind of algorithms search for a better solution by exploring the “neighborhood” of the initial one. This solution becomes the current solution and the local search goes on by exploring its neighborhood. The algorithm stops when the current neighborhood does not furnish a better value and the current solution is called “local optimum”.

In an intuitive way, the larger the neighborhood is, the better is the quality of the local optimum. But, the larger the neighborhood is, the longer is needed to explore it. For this reason, a larger neighborhood is in practice interesting only when it can be explored in an efficient way. The article of Ahuja et al. [18] present a survey of very large-scale neighborhoods. It focuses on exponential neighborhoods (in the size of the initial instance) where the best neighbor can be found in polynomial time. Unlike these algorithms, the exponential neighborhood search we present in this article has a pseudo-polynomial complexity.

Congram et al. [19] have introduced the Dynasearch search algorithm for the one-machine problem where the objective function is to minimize the sum of the weighted tardiness. While neighbors are usually derived from the current solution by a single transformation, Dynasearch neighbors are obtained by several simultaneous “independent” job exchanges. Sourd [20] has studied the single machine problem with release dates and setup times, 1|ri,setup|i(αiEi+βiTi) with this neighborhood technique (ri is the release date of job i). He proves that the exploration of the Dynasearch neighborhood for this problem is NP-hard. Nevertheless, it can be explored in a pseudo-polynomial time.

Since the problem we study in this article, Pdi=driαiEi+βiTi, is NP-hard in the strong sense, our purpose is to define a neighborhood in order to propose a local search algorithm. This neighborhood is called “exponential” since the number of neighbor schedules of a given schedule S can be exponential. This exponential neighborhood is based on job exchanges: an early job is inserted late in the same machine or in another; a late job is inserted early in any machine; an early job is transferred early to another machine; and finally, a tardy job is transferred late to another machine. Similarly to Dynasearch, the definition of the neighbor will rely on several independent job exchanges. In this paper we usually say “search or explore” the neighborhood and we mean finding the minimum cost schedule in the neighborhood of a given schedule.

Section 1 surveys the properties of the dominant schedules of the problem P|di=dr|i(αiEi+βiTi). The exponential neighborhood and the local search algorithm (based on dynamic programming) are presented in Section 2. In Section 3 we show that finding the best schedule in the exponential neighborhood is an NP-hard problem. Finally, some computational tests are presented in Section 4.

Section snippets

V-shaped schedule

The class of dominant schedules of the identical parallel machine problem with restrictive common due date and job-dependent earliness and tardiness penalties, P|di=dr|i(αiEi+βiTi), inherits some well known properties from the single machine problem with restrictive common due date. A schedule that verifies the following properties is a V-shaped schedule.

Property 1

As for the single machine problem, an optimal schedule has no inserted idle time between the execution of the jobs (it can be proved by

Exponential neighborhood

In this section we first define the exponential neighborhood for the one-machine problem with a restrictive common due date and general earliness and tardiness penalties, 1|di=dr|i(αiEi+βiTi). Then, for a given initial schedule S, we propose an algorithm that finds the best schedule in this exponential neighborhood. Later, based on the one-machine neighborhood, we define the exponential neighborhood for the parallel machine problem and an algorithm to explore it.

Complexity of the neighborhood search

In Section 2.2 we have shown how to determine the best schedule in neighborhood V(S) in pseudo-polynomial time. For the sake of completeness, we show now that this problem is NP-hard even if we only consider neighborhood V1(S) corresponding to the single machine case and αi=βi=1 for all task i.

Formally, we consider the following problem P. Given a set of n jobs that have a restrictive common due date dr, penalties αi=βi=1 for all i=1,,n, a V-shaped schedule SINI of the jobs specified by two

Experimental results

The purpose of this section is to point out the quality and the efficiency of the solutions obtained by the exponential neighborhood search we presented in the previous sections.

Conclusions

We have studied a scheduling problem on identical parallel machines with earliness-tardiness penalties and a restricted common due date, P|di=dr|i(αiEi+βiTi). Since this problem is NP-hard in the strong sense we proposed a neighborhood search algorithm. The particularity of the neighborhood we defined is its exponential size. We proved that searching the schedule with less cost in the neighborhood of a given schedule is an NP-hard problem. Nevertheless, we proposed a pseudo-polynomial dynamic

References (28)

  • R. Ahuja et al.

    A survey of very large-scale neighborhood search techniques

    Discrete Applied Mathematics

    (2002)
  • J. Hoogeveen et al.

    Scheduling around a small common due date

    European Journal of Operational Research

    (1991)
  • D. Biskup et al.

    Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates

    Computers and Operations Research

    (2001)
  • C. Hino et al.

    Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

    European Journal of Operational Research

    (2005)
  • Cited by (15)

    • Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review

      2020, Computers and Industrial Engineering
      Citation Excerpt :

      Later,Alvarez-Valdes et al. (2015) show two metaheuristic frameworks: path re-linking and scatter search, which combine solutions obtained through a constructive and local search process. To assess the performance of the algorithms, they use the benchmarks reported inRios-Solis and Sourd (2008) and claim that improved solutions were found. More recently,Lin et al. (2016) test a fast ruin-and-recreate algorithm and compare with the algorithms reported byAlvarez-Valdes et al. (2015) using the same test set, however, they did not apply the same experiment conditions (the codes were run in different computers with different processors).

    • Split-merge: Using exponential neighborhood search for scheduling a batching machine

      2015, Computers and Operations Research
      Citation Excerpt :

      Brueggemann and Hurink [18] consider a single-machine setting with release dates to minimize the total completion time, introducing a very large-scale neighborhood that is searched in polynomial time. Rios-Solis and Sourd [17] consider a parallel machine scheduling problem with earliness and tardiness penalties, and proposed a pseudo-polynomial algorithm to explore an exponential neighborhood. Brueggemann and Hurink [22] also consider a parallel machine setting, but with the objective of minimizing the total weighted completion time, developing and evaluating very large-scale neighborhoods.

    • Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics

      2015, Computers and Operations Research
      Citation Excerpt :

      One of them, LagRes, based on the Lagrangean Relaxation of a time-indexed formulation of the problem, obtained very good results in short computer times. This bound has been used by Rios-Solis and Sourd [11] in their study of the problem with common due-date. Table 12 shows the average percentage distance between the result obtained by our algorithms for each instance and the corresponding value of the lower bound provided by Rios-Solis and Sourd.

    View all citing articles on Scopus
    1

    Partial funding provided by CONACyT, the Mexican National Council of Science and Technology.

    View full text