American Institute of Mathematical Sciences

April  2019, 15(2): 577-593. doi: 10.3934/jimo.2018058

An uncertain programming model for single machine scheduling problem with batch delivery

 School of Science, Nanjing University of Science and Technology, Nanjing 210094, Jiangsu, China

* Corresponding author: Yuanguo Zhu

Received  August 2017 Revised  January 2018 Published  April 2018

A single machine scheduling problem with batch delivery is studied in this paper. The objective is to minimize the total cost which comprises earliness penalties, tardiness penalties, holding and transportation costs. An integer programming model is proposed and two dominance properties are obtained. However, sometimes due to the lack of historical data, the worker evaluates the processing time of a job according to his past experience. A pessimistic value model of the single machine scheduling problem with batch delivery under an uncertain environment is presented. Since the objective function is non-monotonic with respect to uncertain variables, a hybrid algorithm based on uncertain simulation and a g#enetic algorithm (GA) is designed to solve the model. In addition, two dominance properties under the uncertain environment are also obtained. Finally, computational experiments are presented to illustrate the modeling idea and the effectiveness of the algorithm.

Citation: Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
References:

show all references

References:
An example of crossover
An example of mutation
The sensitivity of the solution with respect to the confidence level
List of notations
 notations definitions $i=1, 2, ..., n$ the index of job $j=1, 2, ...$ the index of position $b=1, 2, ...$ the index of batch $l=1, 2, ...$, K the index of customer $n_{l}$ the number of jobs of customer $l$, l=1, 2, ..., K $p_i$ processing time of job $i$, i=1, 2, ..., n $[d^{s}_{i}, d^{t}_{i}]$ due window of job $i$, i=1, 2, ..., n $\alpha_i$ unit earliness penalty cost of job $i$, i=1, 2, ..., n $\beta_i$ unit tardiness penalty cost of job $i$, i=1, 2, ..., n $h_i$ unit holding cost of job $i$, i=1, 2, ..., n $D_l$ transportation cost of customer $l$, l=1, 2, ..., K $C_i$ completion time of job $i$, i=1, 2, ..., n $T_j$ completion time of the $j$th job on machine}, j=1, 2, ... $R_i$ delivery date of job $i$, i=1, 2, ..., n $R^{'}_{lb}$ delivery date of the $b$th batch of customer $l$, l=1, 2, ..., K; b=1, 2, ...
 notations definitions $i=1, 2, ..., n$ the index of job $j=1, 2, ...$ the index of position $b=1, 2, ...$ the index of batch $l=1, 2, ...$, K the index of customer $n_{l}$ the number of jobs of customer $l$, l=1, 2, ..., K $p_i$ processing time of job $i$, i=1, 2, ..., n $[d^{s}_{i}, d^{t}_{i}]$ due window of job $i$, i=1, 2, ..., n $\alpha_i$ unit earliness penalty cost of job $i$, i=1, 2, ..., n $\beta_i$ unit tardiness penalty cost of job $i$, i=1, 2, ..., n $h_i$ unit holding cost of job $i$, i=1, 2, ..., n $D_l$ transportation cost of customer $l$, l=1, 2, ..., K $C_i$ completion time of job $i$, i=1, 2, ..., n $T_j$ completion time of the $j$th job on machine}, j=1, 2, ... $R_i$ delivery date of job $i$, i=1, 2, ..., n $R^{'}_{lb}$ delivery date of the $b$th batch of customer $l$, l=1, 2, ..., K; b=1, 2, ...
Results for small scale
 No GA HGA min max time(s) min max time(s) 1 3079 3361 356 3125 3349 301 2 2953 3415 338 2837 3437 312 3 2556 2889 313 2398 2735 263 4 3582 3764 359 3619 3923 329 5 2046 2358 271 2098 2491 254
 No GA HGA min max time(s) min max time(s) 1 3079 3361 356 3125 3349 301 2 2953 3415 338 2837 3437 312 3 2556 2889 313 2398 2735 263 4 3582 3764 359 3619 3923 329 5 2046 2358 271 2098 2491 254
Results for mesoscale
 No GA HGA min max time(s) min max time(s) 1 8466 8893 1603 8501 8697 1354 2 9320 9671 1754 9455 9612 1340 3 8323 8569 1625 8361 8538 1385 4 8736 9028 1701 8798 9110 1313 5 7954 8077 1590 7839 8154 1397
 No GA HGA min max time(s) min max time(s) 1 8466 8893 1603 8501 8697 1354 2 9320 9671 1754 9455 9612 1340 3 8323 8569 1625 8361 8538 1385 4 8736 9028 1701 8798 9110 1313 5 7954 8077 1590 7839 8154 1397
Results for large scale
 No GA HGA min max time(s) min max time(s) 1 21542 22634 8655 21696 21873 6320 2 19556 21391 8367 19374 20065 5966 3 21406 23767 8961 21250 22034 6257 4 21973 23891 9058 21630 22741 6299 5 20592 22378 8537 20063 20097 6035
 No GA HGA min max time(s) min max time(s) 1 21542 22634 8655 21696 21873 6320 2 19556 21391 8367 19374 20065 5966 3 21406 23767 8961 21250 22034 6257 4 21973 23891 9058 21630 22741 6299 5 20592 22378 8537 20063 20097 6035
Average relative percentage errors of GA and HGA
 $n$ GA HGA $20$ $0.06266$ $0.05713$ $50$ $0.03316$ $0.02685$ $100$ $0.01295$ $0.007372$ $200$ $0.005723$ $0.004993$ Average $0.028623$ $0.024086$
 $n$ GA HGA $20$ $0.06266$ $0.05713$ $50$ $0.03316$ $0.02685$ $100$ $0.01295$ $0.007372$ $200$ $0.005723$ $0.004993$ Average $0.028623$ $0.024086$
 [1] Lifen Jia, Wei Dai. Uncertain spring vibration equation. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021073 [2] Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393 [3] Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182 [4] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044 [5] Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044 [6] Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045 [7] Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065 [8] Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016 [9] Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008 [10] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081 [11] Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004 [12] Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040 [13] Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046 [14] Yi Peng, Jinbiao Wu. Analysis of a batch arrival retrial queue with impatient customers subject to the server disasters. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2243-2264. doi: 10.3934/jimo.2020067 [15] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [16] Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 [17] Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205 [18] Simone Fiori, Italo Cervigni, Mattia Ippoliti, Claudio Menotta. Synthetic nonlinear second-order oscillators on Riemannian manifolds and their numerical simulation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021088 [19] Bouthaina Abdelhedi, Hatem Zaag. Single point blow-up and final profile for a perturbed nonlinear heat equation with a gradient and a non-local term. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021032 [20] Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010

2019 Impact Factor: 1.366

Metrics

• HTML views (1497)
• Cited by (1)

• on AIMS