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

*(English)*Zbl 1438.90116Summary: 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 genetic 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.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C10 | Integer programming |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

single machine scheduling; batch delivery; uncertain environment; genetic algorithm; uncertain simulation
PDF
BibTeX
XML
Cite

\textit{J. Shen} and \textit{Y. Zhu}, J. Ind. Manag. Optim. 15, No. 2, 577--593 (2019; Zbl 1438.90116)

Full Text:
DOI

##### References:

[1] | E. Cakici; S. Mason; M. Kurz, Multi-objective analysis of an integrated supply chain scheduling problem, International Journal of Production Research, 50, 2624-2638, (2012) |

[2] | Y. Chen and Y. Zhu, Indefinite LQ optimal control with process state inequality constraints for discrete-time uncertain systems Journal of Industrial and Management Optimization, to appear. |

[3] | T. Cheng; V. Gordon; M. Kovalyov, Single machine scheduling with batch deliveries, European Journal of Operational Research, 94, 227-283, (1996) · Zbl 0947.90579 |

[4] | Q. Cui; Y. Sheng, Uncertain programming model for solid transportation problem, Information: An International Interdisciplinary Journal, 16, 1207-1214, (2013) |

[5] | J. Framinan; P. Gonzalez, On heuristic solutions for the stochastic flow shop scheduling problem, European Journal of Operational Research, 246, 413-420, (2015) · Zbl 1346.90403 |

[6] | B. Fu; Y. Huo; H. Zhao, Coordinated scheduling of production and delivery with production window and delivery capacity constraints, Theoretical Computer Science, 422, 39-51, (2012) · Zbl 1237.90089 |

[7] | Y. Gao, Shortest path problem with uncertain arc lengths, Computers & Mathematics with Applications, 62, 2591-2600, (2011) · Zbl 1231.90367 |

[8] | Y. Gao; L. Yang; S. Li, Uncertain Models on railway transportation planning problem, Applied Mathematical Modelling, 40, 4921-4934, (2016) |

[9] | N. Hall; M. Lesaoana; C. Potts, Scheduling with fixed delivery dates, Operations Research, 49, 134-144, (2001) · Zbl 1163.90459 |

[10] | N. Hall; C. Potts, Supply chain scheduling: Batching and delivery, Operation research, 51, 566-584, (2003) · Zbl 1165.90455 |

[11] | N. Hall; C. Potts, The coordination of scheduling and batch deliveries, Annals of Operations Research, 135, 41-64, (2005) · Zbl 1112.90022 |

[12] | R. Hallah, Minimizing total earliness and tardiness on a single machine using a hybrid heuristic, Computers & Operations Research, 34, 3126-3142, (2007) · Zbl 1185.90088 |

[13] | A. Hamidinia; S. Khakabimamaghani; M. Mazdeh; M. Jafari, A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system, Computers & Industrial Engineering, 62, 29-38, (2012) |

[14] | S. Han; Z. Peng; S. Wang, The maximum flow problem of uncertain network, Information Sciences, 265, 167-175, (2014) · Zbl 1328.90018 |

[15] | X. Hao; L. Lin; M. Gen; K. Ohno, Effective estimation of distribution algorithm for stochastic job shop scheduling problem, Procedia Computer Science, 20, 102-107, (2013) |

[16] | G. Jiang, An uncertain chance-constrained programming model for empty container allocation, Information: An International Interdisciplinary Journal, 16, 1119-1124, (2013) |

[17] | F. Jolai; M. Rabbani; S. Amalnick; A. Dabaghi; M. Dehghan; M. YazdanParas, Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs, Applied Mathematics & Computation, 194, 552-560, (2007) · Zbl 1193.90102 |

[18] | S. Karimi; Z. Ardalan; B. Naderi; M. Mohammadi, Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm, Applied Mathematical Modelling, 47, 667-682, (2017) |

[19] | H. Ke; J. Ma; G. Tian, Hybrid multilevel programming with uncertain random parameters, Journal of Intelligent Manufacturing, 28, 589-596, (2017) |

[20] | S. Li; J. Peng, A new approach to risk comparison via uncertain measure, Industrial Engineering and Management Systems, 11, 176-182, (2012) |

[21] | B. Liu, Uncertainty Theory, Springer-Verlag, Berlin, 2004. |

[22] | B. Liu, Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer-Verlag, Berlin, 2010. |

[23] | B. Liu; K. Yao, Uncertain multilevel programming: algorithm and applications, Computers & Industrial Engineering, 89, 235-240, (2015) |

[24] | B. Liu, Some research problems in uncertainty theory, Journal of Uncertain Systems, 3, 3-10, (2009) |

[25] | A. Mason; E. Anderson, Minimizing flow time on a single-machine with job classes and setup times, Naval Research Logistic, 38, 333-350, (1991) · Zbl 0747.90049 |

[26] | Y. Ning; X. Chen; Z. Wang; X. Li, An uncertain multi-objective programming model for machine scheduling problem, International Journal of Machine Learning and Cybernetics, 8, 1493-1500, (2017) |

[27] | Z. Peng; K. Iwamura, A sufficient and necessary condition of uncertainty distribution, Journal of Interdisciplinary Mathematics, 13, 277-285, (2010) · Zbl 1229.28029 |

[28] | X. Qi, Coordinated logistics scheduling for in-house production and outsourcing, IEEE Transactions on Automation Science and Engineering, 5, 188-192, (2008) |

[29] | L. Rong, Two new uncertainty programming models of inventory with uncertain costs, Journal of Information & Computational Science, 8, 280-288, (2011) |

[30] | J. Shen; Y. Zhu, Scheduling in a two-stage supply chain with uncertain parameters, Journal of Intelligent and Fuzzy Systems, 30, 3439-3449, (2016) · Zbl 1361.90022 |

[31] | A. Singh; J. ValenteMaria; M. Moreira, Hybrid heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, International Journal of Machine Learning and Cybernetics, 3, 327-333, (2012) |

[32] | A. Soukhal; A. Oulamara; P. Martineau, Complexity of flow shop scheduling problems with transportation constraints, European Journal of Operational Research, 161, 32-41, (2005) · Zbl 1065.90043 |

[33] | K. Stecke; X. Zhao, Production and transportation integration for a make-todelivery business mode, Manufacturing & Service Operations Management, 9, 206-224, (2007) |

[34] | G. Steiner; R. Zhang, Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains, Journal of Scheduling, 12, 565-574, (2009) · Zbl 1182.90050 |

[35] | G. Wan; B. Yen, Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties, European Journal of Operational Research, 142, 271-281, (2002) · Zbl 1082.90531 |

[36] | X. Wang; T. Cheng, Logistics scheduling to minimize inventory and transport costs, International Journal of Production Economics, 121, 266-273, (2009) |

[37] | X. Wang; T. Cheng, Production scheduling with supply and delivery considerations to minimize the makespan, European Journal of Operational Research, 194, 743-752, (2009) · Zbl 1162.90017 |

[38] | X. Wu; X. Zhou, Stochastic scheduling to minimize expected maximum lateness, European Journal of Operational Research, 190, 103-115, (2008) · Zbl 1146.90431 |

[39] | H. Yan; Y. Sun; Y. Zhu, A linear-quadratic control problem of uncertain discretr-time switched systems, Journal of Industrial and Management Optimization, 13, 267-282, (2017) · Zbl 1368.49041 |

[40] | X. Yang, Scheduling with generalized batch delivery dates and earliness penalties, IIE Transactions, 32, 735-741, (2000) |

[41] | K. Yao, Multi-dimensional uncertain calculus with liu process, Journal of Uncertain Systems, 8, 244-254, (2014) |

[42] | Y. Yin; T. Cheng; S. Cheng; C. Wu, Single-machine batch delivery scheduling with an assignable common due date and controllable processing times, Computers & Industrial Engineering, 65, 652-662, (2013) |

[43] | Y. Yin; T. Cheng; C. Wu; S. Cheng, Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times, International Journal of Production Research, 51, 5083-5099, (2013) |

[44] | Y. Yin; T. Cheng; C. Hsu; C. Wu, Single-machine batch delivery scheduling with an assignable common due window, Omega, 41, 216-225, (2013) |

[45] | Y. Yin, T. Cheng, C. Wu and S. Cheng, Single-machine batch delivery scheduling and common due-date assignment with a rate-modifying activity, International Journal of Production Research, 52 (2014), 5583-5596. |

[46] | Y. Yin; Y. Wang; T. Cheng; D. Wang; C. Wu, Two-agent single-machine scheduling to minimize the batch delivery cost, Computers & Industrial Engineering, 92, 16-30, (2016) |

[47] | S. Zdrzalka, Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times, European Journal of Operational Research, 51, 199-209, (1991) · Zbl 0741.90038 |

[48] | Y. Zhu, Functions of uncertain variables and uncertain programming, Journal of Uncertain Systems, 6, 278-288, (2012) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.