Abstract
We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:
1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.
2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.
3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.
4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.
5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.
A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
T.C.E. Cheng M.Y. Kovalyov (1995) ArticleTitle“Single Machine Batch Scheduling with Deadlines and Resource Dependent Processing Times” Operations Research Letters 21 243–249 Occurrence Handle1357082
T.C.E. Cheng Adam Janiak M.Y. Kovalyov (1998) ArticleTitle“Bicriterion Single Machine Scheduling with Resource Dependent Processing Times” SIAM Journal Optimization 8 IssueID2 617–630 Occurrence Handle0907.68113
T.C.E. Cheng Adam Janiak M.Y. Kovalyov (2001) ArticleTitle“Single Machine Batch Scheduling with Resource Dependent Setup and Processing Times” European Journal of Operational research 135 177–183 Occurrence Handle1077.90525 Occurrence Handle1853962
G. Dobson U. S. Karmarkar J. L. Rummel (1987) ArticleTitle“Batching to Minimize Flow Times on One Machine” Management Science 33 784–799 Occurrence Handle10.1287/mnsc.33.6.784 Occurrence Handle0624.90047
Sangsu Han Hiroaki Ishii Susumu Fujii (1994) ArticleTitle“One Machine Scheduling Problem with Fuzzy Due-Dates” European Journal of Operational Research 79 1–12 Occurrence Handle0816.90082
Kanthen K. Harikrishnan H. Ishii (2001) ArticleTitle“Some Resource Constrained Scheduling Problems” Asia Pacific Management Review 6 477–484
E.L. Lawler J.M. Moore (1969) ArticleTitleA Functional Equation and its Applications to Resource Allocation and Sequencing Problems” Management Science 16 77–84 Occurrence Handle0184.23303
Kanesan Muthusamy Hiroaki Ishii Teruo Masuda Shintaro Mohri (2002) ArticleTitle“Single Machine Batching Problem to Minimize the Sum o Completion Times with Number of Batches and Batch Size Limitations” Science Mathematicae Japonicae 55 369–381 Occurrence Handle1004.90039 Occurrence Handle1887071
D. Naddef C. Santos (1988) ArticleTitle“One-Pass Batching Algorithms for the One-Machine Problem” Discrete Applied Mathematics 21 133–145 Occurrence Handle0661.90044 Occurrence Handle959425
C. N Potts M. Y. Kovalyov (2000) ArticleTitle“Scheduling with Batching: A Review” European Journal of Operational Research 120 228–249 Occurrence Handle10.1016/S0377-2217(99)00153-8 Occurrence Handle0953.90028 Occurrence Handle1785709
D. F. Shallcross (1992) ArticleTitle“A Polynomial Algorithm for a One Machine Batching Problem” Operations Research Letters 11 213–218 Occurrence Handle0760.90059 Occurrence Handle1183669
C.S. Sung U.G. Joo. (1997) ArticleTitle“Batching to Minimize Weighted Mean Flow Time on a Single Machine with Batch Size Restrictions” Computers and Industrial Engineering 32 333–340
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Harikrishnan, K.K., Ishii, H. Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date. Fuzzy Optim Decis Making 4, 141–147 (2005). https://doi.org/10.1007/s10700-004-5870-9
Issue Date:
DOI: https://doi.org/10.1007/s10700-004-5870-9