حداکثرسازی پاداش در مشکل جابجایی با تاریخ های مقرر تعمیم یافته

The relocation problem, based on a public housing project in Boston, USA, is a generalized resource-constrained scheduling problem in which the amount of resources (new housing units) returned by a completed job (building) is not necessarily the same as the amount of resources (original housing units) it started out with for processing. In this paper we consider a variant where several generalized due dates are specified to define the number of new housing units that should be built in the entire duration of the project. Generalized due dates are different from conventional due dates in that they are job independent and common to all jobs. In the present study each generalized due date is given to specify an expected percentage of completion of the project. Given an initial number of temporary housing units, the goal is to find a feasible reconstruction sequence that maximizes the total reward over all generalized due dates. This paper investigates the time complexity of the problem. Two upper bounds and a dominance property are proposed for the design of branch-and-bound algorithms. Computational experiments are carried out to assess the efficiency of the proposed properties. The results show that the proposed properties can significantly reduce the time required for producing an optimal schedule.

Resource constraints are one of the issues that are the most commonly addressed in project scheduling and management (Al-Fawzan and Haouari, 2005; Drezet and Billaut, 2008; Kobylański and Kuchta, 2007; Mingozzi et al., 1998; Pesenti and Ukovich, 2003). The study on the relocation problem arose from a public housing redevelopment project in Boston (PHRG, 1986; Kaplan, 1986). The goals of the project were to tear down some old buildings and build new ones in the same area. For this housing redevelopment scheme, the authorities provided sufficient temporary housing units for the tenants who would be evacuated from the area being redeveloped. More specifically, the authorities wanted a construction sequence of the new buildings and when and where all the displaced tenants were to be housed during the redevelopment process. This relocation problem can be looked at from an optimization point of view, in order to determine the minimum initial budget guaranteeing a feasible redevelopment sequence of the buildings. In this paper, we will consider a variant of the relocation problem that takes into account check points of the redevelopment. In most scheduling problems, the due dates are job-dependent. That is, each due date is associated with a particular job and each individual job is expected to be completed before its corresponding due date. Hall (1986) first introduced the concept of generalized due dates. When scheduling using generalized due dates, the due dates are job independent such that a generalized due date is associated with a certain number of jobs that must be completed prior to that point in time. The idea of generalized due dates is commonly adopted in the real world. For example, a company might have a 2-year contract to produce 100 units of a product with the special requirement that one batch of 40 units must be delivered within the first year. In this paper, we focus on the relocation problem incorporating generalized due dates. Consider the original setting of the relocation problem in the housing redevelopment project. The authorities and the construction company may set several generalized due dates based upon which they coordinate their transactions, such as pay by installments, project reviews, and so on. In this paper, we define a generalized due date as the time by which an expected percentage of the project is to be completed. For example, 50% of the newly built capacities of the project must be completed within the first year, and the entire project shall be completed at the end of the second year. At each generalized due date, if the actual percentage of the completion of the project is less than that is expected, the authorities may reduce the amount paid to the construction company as a penalty for the delay. On the other hand, it increases the amount paid as a reward for a more rapid progress. Such type of contract is quite common in the real world (Lock, 1996). For both theoretical and practical considerations, our study will investigate this situation. This paper is organized into seven sections. In Section 2, we present a formal definition of the relocation problem with generalized due dates. This is followed by a literature review on the relocation problem and generalized due dates in Section 3. In Section 4, we present a proof of NP-hardness for the problem considered. Section 5 is dedicated to the design of two upper bounds and one dominance rule for developing a branch-and-bound algorithm. The computational experiments and numerical results are given in Section 6. Finally, we draw our conclusions in Section 7.

In this paper, we studied the 1|rp, gdd|ΣBk problem, which incorporates the concept of generalized due dates in the relocation problem. This problem demonstrates both theoretical and practical significance. For the 1|rp, gdd|ΣBk problem, we have shown its strong NP-hardness by a polynomial-time reduction from 3-Partition. To derive optimal solutions, we developed two upper bounds and one dominance rule as the main ingredients of branch-and-bound algorithms. We designed and conducted computational experiments to study the efficiency of the proposed properties. The numerical results show that the proposed properties can significantly reduce the time (also, the number of nodes generated in the enumeration tree) required for producing optimal solutions. In addition, the synergy effects introduced by the joint deployment of these properties are very informative. Even though the proposed properties can prune unnecessary explorations during the solution-finding process to a certain degree, the problem scale that our algorithm can solve to optimality is still limited. Therefore, there is considerable room for developing more efficient properties so that optimal solutions of larger problems can be derived in an acceptable time. One possible approach for coping with the 1|rp, gdd|ΣBk problem could be the development of Lagrangian relaxation. As mentioned earlier, the 1|rp, gdd|ΣBk problem remains NP-hard even if all jobs require the same processing time and only one gdd is given. However, there is no clue to the existence of a pseudo-polynomial time dynamic program. Therefore, whether the 1|rp, pi=p, Di=D|ΣBk problem is weakly NP-hard remains open. For further study, considering generalized relocation problems, say with new machine environments or new performance measures, could be a worthy direction because the relocation problem is a new type of resource-constrained scheduling problem. The introduction of gdds also opens up a new area of scheduling research, that is, to investigate classical scheduling problems with the consideration of gdds.