Common due-window assignment and minmax scheduling with resource allocation and group technology on a single machine

Abstract

This article considers the minmax common due-window assignment in group scheduling with resource allocation on a single machine. In this problem, jobs are partitioned into groups. In a group, all jobs are processed contiguously, and a common due-window is assigned to them. First, a case with constant processing times is examined. The objective is to minimize the sum of the maximal costs arising from the common due-window among the jobs in each group. This problem is proved to be polynomially solvable. Next, the problem is extended to the case that includes resource allocation. The processing time of each job is considered as either a linear or a convex function of the quantity of resource allocation. The objective function considers the total resource-consumption cost and sum of the maximal costs. For the special case of group-position-dependent penalties, polynomial-time solutions are presented.

KEYWORDS:

• Controllable processing times
• due-window assignment
• group scheduling
• minmax
• resource allocation

Data availability statement

Data sharing is not applicable to this article as no new data were created or analysed in this study.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Major Program of National Science Foundation of China [71790614] and the 111 Project [B16009].