Abstract
This paper describes a single-machine scheduling problem of maximizing total job value with a machine availability constraint. The value of each job decreases over time in a stepwise fashion. Several solution properties of the problem are developed. Based on the properties, a branch-and-bound algorithm and a heuristic algorithm are derived. These algorithms are evaluated in the computational study, and the results show that the heuristic algorithm provides effective solutions within short computation times.
The online version of this article is available Open Access
Introduction
It is quite often to have the situation where all the associated jobs are not completed due to a working hour limit or a production capacity limit. However, all the associated jobs are supposed to be completed in traditional scheduling problems with regular performance measures such as makespan, total tardiness and total completion time (Pinedo, Citation2012). In this research, a non-regular performance measure (i.e., total job value) is presented and maximized on the assumption that a machine does not have to complete all jobs.
The values of jobs in this paper deteriorate over time. It can be used to represent customer satisfaction that deteriorates with the increase in waiting time for the service (Bielen and Demoulin, Citation2007; van Riel et al, Citation2012; Borges et al, Citation2015).
The proposed situation can be illustrated by a repair service example for air conditioners. During hot summer, a mechanic is not able to accommodate all repair requests for the broken air conditioners within work hours. Based on the data collected, the repair firm knows how customer satisfaction decreases with the increase in waiting time. With this information, the repair firm may be interested in maximizing total satisfaction of the customers assigned to a mechanic.
This research is based on two broad branches of scheduling literature: job selection and job deterioration.
A thorough review on job selection and scheduling literature is given in Slotnick (Citation2011) and Shabtay et al (Citation2013). Several topics are introduced to capture a characteristic of the literature. Job selection was mainly used to maximize total profit (or revenue) under a limited processing capacity (Lin and Ying, Citation2013, Citation2015; Reisi-Nafchi et al, Citation2015; Zhang et al, Citation2016). Some papers focused on minimizing the completion time of the last accepted job penalizing the value of rejected jobs (Bartal et al, Citation2000; Zhong et al, Citation2014; Ou et al, Citation2015). A few papers considered the trade-off between the cost to use an expensive machine and the service level. The service level increases as the processing time on the expensive machine increases. Therefore, jobs are selected to find the maximal trade-off (Thevenin et al, Citation2015, Citation2016).
As seen in the above-referenced work, job selection is employed to consider a production capacity limit or/and a time-related penalty. Likewise, this paper selects jobs to consider time-dependent job value with a machine availability constraint.
The scheduling literature describes the deterioration of jobs in two different ways. The first way is to define jobs whose processing times increase as their delays for processing increase (Voutsinas and Pappis, Citation2010). Most work in the area of deteriorating jobs focused on this description (Wang et al, Citation2011). However, like the repair service example for air conditioners, the deterioration of jobs may not increase the processing times of jobs. Therefore, another way to describe the deterioration of jobs appeared in the literature, that is, to define jobs whose values decrease over time. In Voutsinas and Pappis (Citation2002, Citation2010), the values of jobs decrease in an exponential fashion. In Janiak and Krysiak (Citation2007), the values of jobs decrease in a stepwise fashion.
Following Janiak and Krysiak (Citation2007), this paper uses a stepwise value function, taking advantage of its robustness in approximating any type of value functions. However, Janiak and Krysiak (Citation2007) assume that all jobs should be completed, while this paper employs job selection with a machine availability constraint that may be in practice.
The scheduling problem is described in Section 2. Some solution properties of the problem are developed in Section 3. Based on the properties, a branch-and-bound algorithm and a heuristic algorithm are derived in Sections 4 and 5, respectively. The numerical experiments to evaluate the performance of the algorithms are presented in Section 6. Finally, some concluding remarks are made in Section 7.
Problem description
A set of jobs is to be scheduled for processing on a single machine where only one job is allowed at a time and the time horizon of from time
to time
is considered, and
is less than the sum of processing times of all jobs. All jobs in
are independent, non-preemptive and available for processing at time zero. Each job
has its processing time
and its job value
which is given as a non-increasing stepwise function represented by the completion time of job
and the same moments of change
for all jobs in the situation where at least one job in
decreases in its value.
is defined as follows:
where
and
.
The objective is to find a schedule that maximizes the total value of jobs (total job value: TJV) completed within the limited machine available time (from time
to time
) under the assumption that the considered jobs do not need all to be processed.
Since the problem under consideration with constant job values that do not depend on the job completion times is equivalent to the problem which is proved NP-hard by Karp (Citation1972), the proposed problem with stepwise job values is also NP-hard.
Problem analysis
Denote by the assigned partial schedule and
the set of jobs not in
but in
Let
denote a time point
in the interval
where
which satisfies the relation
and
denote the difference of job values between two jobs
during the interval
.
Property 1
Given that two unscheduled jobsand
satisfy the following conditions simultaneously, job
precedes job
in the optimal schedule when the optimal schedule contains both jobs, while only job
is selected in the optimal schedule when the optimal schedule contains one job out of two jobs
and
:
,
Proof
Consider the following notations:
| Case 1 | = | (when schedules contains both Given two feasible schedules as shown in Figure , say Figure 1 Structure of two schedules  |
| Case 2 | = | (when schedules contain only one job out of Given two feasible schedules, say |
Let denote the difference of job values between two jobs
at the completion time of job
in a given schedule and
denote the difference of job values between two jobs
at the completion time of job
in a given schedule. The following properties (from Property 2 to Property 5) can be proved in similar way to the proof of Property 1.
Property 2
Given that the following conditions hold inwhere
,
and
are partial schedules and
, TJV of
is greater than or equal to TJV of
:
Property 3
Given that the following conditions hold in the given schedulewhere
,
and
are partial schedules and
, TJV of
is greater than or equal to TJV of
:
Property 4
Given that the following conditions hold in the given schedulewhere
and
are partial schedules and
, TJV of
is greater than or equal to TJV of
:
job
Property 5
Given that the following conditions hold in the given schedulewhere
and
are partial schedules and
, TJV of
is greater than or equal to TJV of
:
job
Branch-and-bound
This section derives a branch-and-bound algorithm, referring to Baker (Citation1974) and Pinedo (Citation2012).
Upper bound
Let represent a subproblem at level
where
specifies the assigned partial schedule in a branching tree and
specifies the number of jobs in the partial schedule
.
is the same as the original problem
except with the first
positions assigned in the partial schedule
. Let
denote the last job of the partial schedule
,
denote the completion time of the last job of the partial schedule
,
denote a time point
in the interval
where
which satisfies the relation
, and
denote the partial schedule in which the partial schedule
is immediately succeeded by job
.
In order to find an upper bound at the subproblem , the algorithm modifies the values of all jobs in set
first. For each job
, all values in the interval
where
are converted to
which is the value of job
in the interval
.
Then, a knapsack problem to maximize TJV with all jobs, having the modified job values, in set and the available time (capacity) constraint given as
is derived. This problem is denoted by Problem ①. To solve Problem ①, Dantzig’s upper bound in Dantzig (Citation1957) and Martello et al (Citation2000) is adopted as follows:
Let denote the number of jobs in set
and
denote the job at
th position in a arbitrary sequence.
Arrange the jobs in set
Find
Calculate an upper bound of Problem ①.
Upper bound of Problem ① =
For the second upper bound at the subproblem , the values of all jobs in set
are also changed but in a different way. For each job
, the job value in each interval
where
is converted to the maximum value, in each interval
where
of all jobs in set
.
After the changes in the job values, the single-machine scheduling problem that maximizes the TJV with all jobs, having the same job values, in set and machine available time
is derived. This problem is denoted by Problem ②.
Lemma 1
The optimal solution of Problem ② is obtained in SPT sequence.
Proof
Suppose that is the optimal schedule that contains job
and job
which is the successor of
, and does not contain job
, where
.
| Case 1 | = | (Comparison between Set |
| Case 2 | = | (Comparison between Since |
By the results of Case 1 and Case 2, without loss of generality, SPT rule give the optimal solution of Problem ②. □
The second upper bound for subproblem is obtained as follows:
While gives a tighter bound when the difference of job values within each
is small,
gives a tighter bound when the decreasing rate of job values is small. The upper bound of subproblem
is defined as:
Branching
A subproblem ( or
) is partitioned into one or more subproblems (
or
) that are defined by sequencing job
in set
right after the partial schedule
if the partial schedule
satisfies the available time constraint. If no job in set
satisfies the available time constraint at the subproblem
,
is a ending node and the partial schedule
is called a trial solution which updates
(lower bound).
To select a subproblem for branching, the depth-first rule is adopted to select the subproblem with the largest and, in the case of tie, the best-first rule is adopted to select the subproblem with the largest
. Moreover, properties (from Property 1 to Property 5) will be used as branching rules.
Bounding
With the original problem , the initial
is computed by a heuristic which will be explained in Section 5. The algorithm calculates the
of the subproblem
at the subproblem
. If the
is greater than the current
, the subproblem
will be branched from the subproblem
. Otherwise, the subproblem
will be fathomed. Moreover, when the algorithm finds a new
, the subproblems whose
are not greater than the new
are also fathomed.
Overall procedure of branch-and-bound algorithm
| Step 1 | = | Obtain the initial |
| Step 2 | = | If active list = |
| Step 3 | = | Check the conditions of Property 1 for all pairs of jobs included in |
| Step 4 | = | Check the conditions of from Property 2 to Property 5 with |
| Step 5 | = | Place |
| Step 6 | = | Eliminate the subproblems whose |
| Step 7 | = | Terminate the algorithm. The lastly updated trial solution is optimal |
Heuristic
The proposed heuristic algorithm consists of two parts. One part is job selection and allocation mechanism. The other one is the interchange mechanism of job positions.
Job selection and allocation
Let denote the set of jobs which can be assigned to the partial schedule
at a dispatching point (a completion time of the partial schedule
). The algorithm selects and assigns a job which has the largest job value divided by its processing time in the situation where each job in set
is processed right after the partial schedule
. Then the algorithm can give the best solution from the dispatching point to the completion time of the selected job. Moreover, any two jobs in the partial schedule
which is made by the above job selection mechanism do not satisfy the conditions of Property 1 and Property 2, because these properties deal with the specific situation such that the jobs having smaller processing times and larger job values precede any other jobs having larger processing times and smaller job values in the optimal solution.
Interchange of job positions
Given the partial schedule , the algorithm can increase the associated TJV by Property 3, Property 4 and Property 5. If a new job is assigned to the partial schedule
, the conditions of those properties are checked with the new assigned job and any other one job existing in the partial schedule
until all pair jobs in the partial schedule
do not satisfy the conditions of all those properties. If the existing job moves backward in its position by interchanging mechanism, the algorithm should check the conditions of Property 2 with the backward-position-changed job and the jobs which are scheduled between the previous and the new position of the backward-position-changed job, by the fact that the new position of the backward-position-changed job was not assigned by job selection mechanism.
Overall procedure of heuristic algorithm
| Step 1 | = | Put all the jobs not included in |
| Step 2 | = | Check |
| Step 3 | = | Add |
| Step 4 | = | If |
| Step 5 | = | If List1 = |
| Step 6 | = | If List2 = |
| Step 7 | = | Check |
| Step 8 | = | If |
| Step 9 | = | Terminate the algorithm. The schedule |
Note that the interchanging mechanism requires time and the job selection mechanism selects less than
jobs. Thus, the time complexity of this algorithm is
.
Computational study
For the numerical experiments, the algorithms are coded in C++ language and tested on a personal computer with a 2.40 GHz Intel Core i7-3630QM processor (8 GB RAM) and evaluated by use of several impact factors including the number of jobs () and the number of intervals (
). In addition, to determine whether the ranges of
and
for
have any influence on the performance of the algorithms, three different range sets are established and shown in Table .
Table 1 Three different range sets for generating and
Instances were generated referring to the data generation scheme used in Hall and Posner (Citation2001) and Kim et al (Citation2009). All instances used in this study are available online at https://www.dropbox.com/s/mjv07qzkttxtfn0/Instances.zip?dl=0. Each takes an integer selected randomly from a discrete uniform distribution.
integer values are generated and used for
where
which is checked whether it satisfies the assumption that the value of at least one job in
decreases at each moment of change.
takes an integer selected randomly from a discrete uniform distribution under the range
. For generating the moments of change, (
) integers are selected without duplicating number under the range
and used for
where
.
The algorithms were tested for 60 problem cases of 10 instances each. In Table , the third, sixth and ninth columns show the average run times of the branch-and-bound (B-&-B) algorithm to give the optimal solution. As increases, the computation of the B-&-B algorithm tends to take more time. The procedure of computing
, in which the number of job values modified for computing
depends on
, accounts for this tendency.
Table 2 Performances of the B-&-B and the heuristic
The fifth, eighth and eleventh columns of Table show the average Gap between the TJV corresponding to the optimal solution of the B-&-B algorithm (TJV of B-&-B) and the TJV corresponding to the heuristic solution (TJV of heuristic):
Minimum average Gap is 0.31% and maximum average Gap is 5.89%. The heuristic algorithm gives quite a good solution, whereas the run time of the heuristic algorithm is short. The average Gap shows a trend such that as increases, the average Gap gets smaller because, with large
, the differences of job values in each interval
are relatively smaller, and thus, the penalty for the non-optimal schedule is small.
In addition, Table shows that there are no distinct trends between three different range sets for and
. The performances of the B-&-B and the heuristic algorithms are indifferent to the ranges for
and
.
Table shows the average number of interchanging job positions by each property in the heuristic algorithm. The number of interchanges by Property 2 is quite small because the job selection mechanism guarantees that any two jobs in the partial schedule do not satisfy the conditions of Property 2, and thus, Property 2 is applicable only to the jobs which is moved its position backward by the interchanging mechanism. Property 3 plays an important role in the interchanging mechanism because Property 3 argues that the jobs which have larger processing times and lower job values can precede other job which has smaller processing times and higher job values in the optimal solution, which is the opposite argument of the job selection mechanism. In the same reason, Property 5 is used more frequently than Property 4. Thus, it is concluded that the job selection mechanism and properties complement each other to give a better solution. Since Property 4 and Property 5 are applicable only to the adjacent pair jobs in the partial schedule
, the number of interchanging job positions by those properties is smaller than the number of interchanging job positions by Property 3.
Table 3 Average number of interchanging job positions by each property in the heuristic
Conclusion
This paper considers a single-machine scheduling problem in which the value of each job decreases over time in a stepwise fashion, and jobs need to be selected for processing due to a machine availability constraint. The problem can be applied to making a service sequence that maximizes total customer satisfaction with limited working hours. Solution properties of the problem are developed. Those properties are used for the branch-and-bound algorithm and the heuristic algorithm to efficiently explore the solution space without debasing the quality of solutions. The computational study shows that the heuristic algorithm is efficient and effective comparing with the performance of the branch-and-bound algorithm. Therefore, the heuristic algorithm may be applied to large-size problems.
As further study, it would be interesting to consider a multiple machine scheduling problem with machine availability constraints. In addition, considering resumable and non-resumable cases under multiperiod limited machine availability is also an interesting issue.
Acknowledgements
The authors sincerely thank the editors and two anonymous reviewers for their insightful comments and suggestions to improve the quality of this paper.
References
- BakerKRIntroduction to Sequencing and Scheduling1974New YorkWiley
- BartalYLeonardiSMarchetti-SpaccamelaASgallJStougieLMultiprocessor scheduling with rejectionSIAM Journal on Discrete Mathematics2000131647810.1137/S0895480196300522
- BielenFDemoulinNWaiting time influence on the satisfaction-loyalty relationship in servicesManaging Service Quality: An International Journal200717217419310.1108/09604520710735182
- BorgesAHerterMMCheatJCIt was not that long!: the effects of the in-store TV screen content and consumers emotions on consumer waiting perceptionJournal of Retailing and Consumer Services2015229610610.1016/j.jretconser.2014.10.005
- DantzigGBDiscrete-variable extremum problemsOperations Research19575226627710.1287/opre.5.2.266
- HallNGPosnerMEGenerating experimental data for computational testing with machine scheduling applicationsOperations Research200149685486510.1287/opre.49.6.854.10014
- JaniakAKrysiakTSingle processor scheduling with job values depending on their completion timesJournal of Scheduling200710212913810.1007/s10951-006-0004-6
- KarpRMMillerREThatcherJWReducibility among combinatorial problemsComplexity of Computer Computations1972New YorkPlenum Press85103
- KimESSungCSLeeISScheduling of parallel machines to minimize total completion time subject to s-precedence constraintsComputers & Operations Research200936369871010.1016/j.cor.2007.10.025
- LinSWYingKCIncreasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithmJournal of the Operational Research Society201364229331110.1057/jors.2012.47
- LinSWYingKCOrder acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardinessApplied Soft Computing20153046247410.1016/j.asoc.2015.01.069
- MartelloSPisingerDTothPNew trends in exact algorithms for the 0–1 knapsack problemEuropean Journal of Operational Research2000123232533210.1016/S0377-2217(99)00260-X
- OuJZhongXWangGAn improved heuristic for parallel machine scheduling with rejectionEuropean Journal of Operational Research2015241365366110.1016/j.ejor.2014.09.028
- PinedoMScheduling: Theory, Algorithms, and Systems20124New York, NJPrentice Hall
- Reisi-NafchiMMoslehiGIntegrating two-agent scheduling and order acceptance problems to maximise total revenue by bounding each agent penalty functionInternational Journal of Services and Operations Management201520335838410.1504/IJSOM.2015.067773
- ShabtayDGasperNKaspiMA survey on offline scheduling with rejectionJournal of Scheduling201316132810.1007/s10951-012-0303-z
- SlotnickSAOrder acceptance and scheduling: a taxonomy and reviewEuropean Journal of Operational Research2011212111110.1016/j.ejor.2010.09.042
- TheveninSZuffereyNWidmerMMetaheuristics for a scheduling problem with rejection and tardiness penaltiesJournal of Scheduling20151818910510.1007/s10951-014-0395-8
- TheveninSZuffereyNWidmerMOrder acceptance and scheduling with earliness and tardiness penaltiesJournal of Heuristics201622684989010.1007/s10732-016-9321-x
- RielACRSemejinJRibbinkDBomert-PetersYWaiting for service at the checkout: negative emotional responses, store image and overall satisfactionJournal of Service Management201223214416910.1108/09564231211226097
- VoutsinasTGPappisCPScheduling jobs with values exponentially deteriorating over timeInternational Journal of Production Economics200279316316910.1016/S0925-5273(02)00110-X
- VoutsinasTGPappisCPA branch and bound algorithm for single machine scheduling with deteriorating values of jobsMathematical and Computer Modelling2010521556110.1016/j.mcm.2009.12.024
- WangJBWangJJJiPScheduling jobs with chain precedence constraints and deteriorating jobsJournal of the Operational Research Society20116291765177010.1057/jors.2010.120
- ZhangXZhouSKosterRVeldeSIncreasing the revenue of self-storage warehouses by optimizing order schedulingEuropean Journal of Operational Research20162521697810.1016/j.ejor.2015.12.044
- ZhongXOuJWangGOrder acceptance and scheduling with machine availability constraintsEuropean Journal of Operational Research2014232343544110.1016/j.ejor.2013.07.032